The excessive concentrations of toxic heavy metals in mine tailings and their very low N content make soil reclamation strategies by phytostabilization difficult. Our objective was to test if the symbiotic association between the legume Anthyllis vulneraria subsp. carpatica and the bacteria Mesorhizobium metallidurans originating from highly polluted mine tailings is able to increase N concentration in soils with contrasting Zn, Pb and Cd contents. Plants of A. vulneraria subsp. carpatica from a mine site and of a non-metallicolous subsp. praeopera from non-polluted soil were inoculated with a metallicolous or a non-metallicolous compatible Mesorhizobium spp. and grown on low and high heavy metal-contaminated soils. In contaminated soil, many nodules were observed when the metallicolous A. vulneraria was inoculated with its rhizobium species M. metallidurans, whereas the non-metallicolous A. vulneraria died after a few weeks regardless of the rhizobium inoculant. Eighty percent of the total nitrogen was derived from biological nitrogen fixation through the association between metallicolous A. vulneraria and the rhizobium grown on metal-enriched soil. The ability of the metallicolous A. vulneraria to develop a high nitrogen fixing potential opens new possibilities for promoting a low-maintenance plant cover and for stabilizing the vegetation in high heavy metal-contaminated soils.