Twenty Mimosa-nodulating bacterial strains from Brazil and Venezuela, together with eight reference Mimosa-nodulating rhizobial strains and two other β-rhizobial strains, were examined by amplified rRNA gene restriction analysis. They fell into 16 patterns and formed a single cluster together with the known β-rhizobia, Burkholderia caribensis, Burkholderia phymatum, and Burkholderia tuberum. The 16S rRNA gene sequences of 15 of the 20 strains were determined, and all were shown to belong to the genus Burkholderia; four distinct clusters could be discerned, with strains isolated from the same host species usually clustering very closely. Five of the strains (MAP3-5, Br3407, Br3454, Br3461, and Br3469) were selected for further studies of the symbiosis-related genes nodA, the NodD-dependent regulatory consensus sequences (nod box), and nifH. The nodA and nifH sequences were very close to each other and to those of B. phymatum STM815, B. caribensis TJ182, and Cupriavidus taiwanensis LMG19424 but were relatively distant from those of B. tuberum STM678. In addition to nodulating their original hosts, all five strains could also nodulate other Mimosa spp., and all produced nodules on Mimosa pudica that had nitrogenase (acetylene reduction) activities and structures typical of effective N2-fixing symbioses. Finally, both wild-type and green fluorescent protein-expressing transconjugant strains of Br3461 and MAP3-5 produced N2-fixing nodules on their original hosts, Mimosa bimucronata (Br3461) and Mimosa pigra (MAP3-5), and hence this confirms strongly that Burkholderia strains can form effective symbioses with legumes.