Rhizobia are soil bacteria able to develop a nitrogen-fixing symbiosis with legumes. They are taxonomically spread among the alpha and beta subclasses of the Proteobacteria. Mimosa pudica, a tropical invasive weed, has been found to have an affinity for beta-rhizobia, including species within the Burkholderia and Cupriavidus genera. In this study, we describe the diversity of M. pudica symbionts in the island of New Caledonia, which is characterized by soils with high heavy metal content, especially of Ni. By using a plant-trapping approach on four soils, we isolated 96 strains, the great majority of which belonged to the species Cupriavidus taiwanensis (16S rRNA and recA gene phylogenies). A few Rhizobium strains in the newly described species Rhizobium mesoamericanum were also isolated. The housekeeping and nod gene phylogenies supported the hypothesis of the arrival of the C. taiwanensis and R. mesoamericanum strains together with their host at the time of the introduction of M. pudica in New Caledonia (NC) for its use as a fodder. The C. taiwanensis strains exhibited various tolerances to Ni, Zn and Cr, suggesting their adaptation to the specific environments in NC. Specific metal tolerance marker genes were found in the genomes of these symbionts, and their origin was investigated by phylogenetic analyses.