The genus Bacillus is a phylogenetically incoherent taxon with members of the group lacking a common evolutionary history. Comprising aerobic and anaerobic spore-forming bacteria, no characteristics are known that can distinguish species of this genus from other similar endospore-forming genera. With the availability of complete genomic data from over 30 different species from this group, we have constructed detailed phylogenetic trees to determine the relationships among Bacillus and other closely related taxa. Additionally, we have performed comparative genomic analysis for the determination of molecular markers, in the form of conserved signature indels (CSIs), to assist in the understanding of relationships among species of the genus Bacillus in molecular terms. Based on the analysis, we report here the identification of 11 and 6 CSIs that clearly differentiate a 'Bacillus subtilis clade' and a 'Bacillus cereus clade', respectively, from all other species of the genus Bacillus. No molecular markers were identified that supported a larger clade within this genus. The subtilis and the cereus clades were also the largest observed monophyletic groupings among species from the genus Bacillus in the phylogenetic trees based on 16S rRNA gene sequences and those based upon concatenated sequences for 20 conserved proteins. Thus, the relationships observed among these groups of species through CSIs are independently well supported by phylogenetic analysis. The molecular markers identified in this study provide a reliable means for the reorganization of the currently polyphyletic genus Bacillus into a more evolutionarily consistent set of groups. It is recommended that the genus Bacillus sensu stricto should comprise only the monophyletic subtilis clade that is demarcated by the identified CSIs, with B. subtilis as its type species. Members of the adjoining cereus clade (referred to as the Cereus clade of bacilli), although they are distinct from the subtilis clade, will also retain the Bacillus genus name as they contain several clinically important species, and their transfer into a new genus could have serious consequences. However, all other species that are currently part of the genus Bacillus and not part of these two clades should be eventually transferred to other genera. We also propose that all novel species of the genus Bacillus must meet minimal requirements, foremost among which is that the branching of the prospective species with the Bacillus sensu stricto clade or the Cereus clade of bacilli should be strongly supported by 16S rRNA gene sequence trees or trees based upon concatenated protein sequences. Additionally, the presence of one or more of the CSIs that are specific for these clades may be used to confirm molecularly the placement of the species into these clades. The identified CSIs, in addition to their usefulness for taxonomic and diagnostic purposes, also provide novel probes for genetic and biochemical studies of these bacteria.