Bacterial classification at higher taxonomic ranks such as the order and family levels is currently reliant on phylogenetic analysis of 16S rRNA and the presence of shared phenotypic characteristics. However, these may not be reflective of the true genotypic and phenotypic relationships of taxa. This is evident in the order Bacillales, members of which are defined as aerobic, spore-forming and rod-shaped bacteria. However, some taxa are anaerobic, asporogenic and coccoid. 16S rRNA gene phylogeny is also unable to elucidate the taxonomic positions of several families incertae sedis within this order. Whole genome-based phylogenetic approaches may provide a more accurate means to resolve higher taxonomic levels. A suite of phylogenomic approaches were applied to re-evaluate the taxonomy of 80 representative taxa of eight families (and six family incertae sedis taxa) within the order Bacillales. This showed several anomalies in the current family and order level classifications including the existence of four Bacillaceae and two Paenibacillaceae “family” clades. Furthermore, the families Staphylococcaceae and Listeriaceae belong to the sister order Lactobacillales. Finally, we propose a consensus phylogenomic approach which may diminish algorithmic biases associated with single approaches and facilitate more accurate classification of a broad range of taxa at the higher taxonomic levels.