Several Bacillus and Paenibacillus species were isolated from Fe and Mn oxide minerals precipitating at a deep subsurface oxic-anoxic interface at Henderson Molybdenum Mine, Empire, CO. The isolates were investigated for their Mn(II)-oxidizing potential and interrogated for possession of the mnxG gene, a gene that codes for a putative Mn(II)-oxidizing enzyme in Bacillus species. Seven of eight Bacillus species were capable of Mn(II) oxidation; however, the mnxG gene was detected in only one isolate. Using sequences of known Bacillus species both with and without amplifiable mnxG genes and Henderson Mine isolates, the 16S rRNA and mnxG gene phylogenies were compared to determine if 16S rRNA sequences could be used to predict the presence or absence of an amplifiable mnxG gene within the genomes of the isolates. We discovered a strong correspondence between 16S rRNA sequence similarity and the presence/absence of an amplifiable mnxG gene in the isolates. The data revealed a complex phylogenetic distribution of the mnxG gene in which vertical inheritance and gene loss influence the distribution of the gene among the Bacillus species included in this study. Comparisons of 16S rRNA and functional gene phylogenies can be used as a tool to aid in unraveling the history and dispersal of the mnxG gene within the Bacillus clade.