The genus Pseudalkalibacillus, created by the reclassification of specific deep-branching Alkalihalobacillus species, exhibits polyphyletic branching. The Genome Taxonomy Database (GTDB) also assigns Pseudalkalibacillus species into two families and three genera. To clarify the evolutionary relationships and classification of Pseudalkalibacillus species, we report detailed investigations using phylogenomic and molecular signature-based approaches. In phylogenomic trees, Pseudalkalibacillus species are distributed within two family-level lineages. One of these clades, containing the type species of Pseudalkalibacillus (viz. Pseudalkalibacillus decolorationis), represents the genus Pseudalkalibacillus, groups within the family Fictibacillaceae. Ten novel conserved signature indels (CSIs) identified in this study are specific for this clade, providing a robust means for the differentiation of the emended genus Pseudalkalibacillus. The remaining Pseudalkalibacillus species form a separate family-level clade, designated as f_HBI72195 in the GTDB. Within this clade, all species except Pseudalkalibacillus caeni form a robust clade designated as Pseudalkalibacillus clade −2 in our work and g_Anaerobacillus_A in the GTDB. We have also identified 15 novel CSIs specific to this clade. As the Pseudalkalibacillus clade −2 is distinct from Pseudalkalibacillus, we propose transferring species from this clade into a new genus, Guptibacillus gen. nov. The species P. caeni branches distinctly from other Pseudalkalibacillus species, and the GTDB considers it a novel genus (g_Bacillus_BR). Six newly identified CSIs are specific to this species, and we are proposing the transfer of this species into a new genus, Exobacillus gen. nov. Two additional identified CSIs are shared by members of the novel family-level taxon (f_HBI72195) comprising the proposed genera Guptibacillus and Exobacillus, for which we are proposing the name Guptibacillaceae fam. nov. Lastly, the results presented here also show that ‘Pseudalkalibacillus hemicentroti’ and ‘Pseudalkalibacillus macyae’ are later heterotypic synonyms of Guptibacillus hwajinpoensis. These changes, which reliably depict the evolutionary relationships among Pseudalkalibacillus species, should be helpful in future studies of these organisms.