The order Sphingomonadales strains are globally distributed in various biomes and are renowned for their biodegradable and biosynthesis capabilities. At present, it consists of 4 families and 49 genera making it the third largest order within the class Alphaproteobacteria. However, their taxonomy remains complex, especially due to polyphyly in the family Sphingomonadaceae. In this study, we collected 429 Sphingomonadales type strain genomes, reconstructed robust phylogenomic relationships, and proposed delineation thresholds at the genus and family levels based on average amino acid identities (AAI) and evolutionary distances (ED). Based on the maximum-likelihood and Bayesian phylogenomic trees reconstructed by two molecular sets determined by orthologous sequence identity and the Genome Taxonomy Database, the consensus degree values were all higher than 90%, revealing that those phylogenomic trees had similar topological structures. By confirming monophyletic taxa and determining stable nodes, we reclassified the order Sphingomonadales into thirteen families including nine novel ones. AAI calculations indicated that the average intra-family AAI values ranged from 0.62 to 0.84, while inter-family ones were 0.51 to 0.60. ED summaries demonstrated that the average and median intra-family ED values were 0.16 to 0.57, and inter-family ones ranged from 0.50 to 1.22. Comparisons of AAI and ED values calculated by using genomic and phylogenetic analyses supported that those 13 families were significantly separated with p values < 2.2×10−16. Thus, it was speculated that the AAI and ED thresholds for distinguishing different families were <0.6 and >0.5, respectively. Additionally, we reclassified 163 species into new genera with their phylogenetic topologies, according to the previous genus AAI and ED boundaries of 0.7 and 0.4. Our study is the first genomic-based study of the order Sphingomonadales and will promote further insights into the evolution of this order.