Genome analysis of fourteen mimosoid and four papilionoid beta-rhizobia together with fourteen reference alpha-rhizobia for both nodulation (nod) and nitrogen-fixing (nif/fix) genes has shown phylogenetic congruence between 16S rRNA/MLSA (combined 16S rRNA gene sequencing and multilocus sequence analysis) and nif/fix genes, indicating a free-living diazotrophic ancestry of the beta-rhizobia. However, deeper genomic analysis revealed a complex symbiosis acquisition history in the beta-rhizobia that clearly separates the mimosoid and papilionoid nodulating groups. Mimosoid-nodulating beta-rhizobia have nod genes tightly clustered in the nodBCIJHASU operon, whereas papilionoid-nodulating Burkholderia have nodUSDABC and nodIJ genes, although their arrangement is not canonical because the nod genes are subdivided by the insertion of nif and other genes. Furthermore, the papilionoid Burkholderia spp. contain duplications of several nod and nif genes. The Burkholderia nifHDKEN and fixABC genes are very closely related to those found in free-living diazotrophs. In contrast, nifA is highly divergent between both groups, but the papilionoid species nifA is more similar to alpha-rhizobia nifA than to other groups. Surprisingly, for all Burkholderia, the fixNOQP and fixGHIS genes required for cbb3 cytochrome oxidase production and assembly are missing. In contrast, symbiotic Cupriavidus strains have fixNOQPGHIS genes, revealing a divergence in the evolution of two distinct electron transport chains required for nitrogen fixation within the beta-rhizobia.