Rhizobia form specialized nodules on the roots of legumes (family Fabaceae) and fix nitrogen in exchange for carbon from the host plant. Although the majority of legumes form symbioses with members of genus Rhizobium and its relatives in class Alphaproteobacteria, some legumes, such as those in the large genus Mimosa, are nodulated predominantly by betaproteobacteria in the genera Burkholderia and Cupriavidus. The principal centers of diversity of these bacteria are in central Brazil and South Africa. Molecular phylogenetic studies have shown that betaproteobacteria have existed as legume symbionts for approximately 50 million years, and that, although they have a common origin, the symbiosis genes in both subclasses have evolved separately since then. Additionally, some species of genus Burkholderia, such as B. phymatum, are highly promiscuous, effectively nodulating several important legumes, including common bean (Phaseolus vulgaris). In contrast to genus Burkholderia, only one species of genus Cupriavidus (C. taiwanensis) has so far been shown to nodulate legumes. The recent availability of the genome sequences of C. taiwanensis, B. phymatum, and B. tuberum has paved the way for a more detailed analysis of the evolutionary and mechanistic differences between nodulating strains of alpha- and betaproteobacteria. Initial analyses of genome sequences have suggested that plant-associated Burkholderia spp. have lower G+C contents than Burkholderia spp. that are opportunistic human pathogens, thus supporting previous suggestions that the plant- and human-associated groups of Burkholderia actually belong in separate genera.