A survey of symbiotic bacteria from legumes grown in high mercury-contaminated soils (Almadén, Spain) was performed to produce a collection of rhizobia which could be well adapted to the environmental conditions of this region and be used for restoration practices. Nineteen Hg-tolerant rhizobia were isolated from nodules of 11 legume species (of the genera Medicago, Trifolium, Vicia, Lupinus, Phaseolus, and Retama) and characterized. Based on their growth on Hg-supplemented media, the isolates were classified into three susceptibility groups. The minimum inhibitory concentrations (MICs) and the effective concentrations that produce 50% mortality identified the patterns of mercury tolerance and showed that 15 isolates were tolerant. The dynamics of cell growth during incubation with mercury showed that five isolates were unaffected by exposure to Hg concentrations under the MICs. Genetic analyses of the 16S rRNA gene assigned ten strains to Rhizobium leguminosarum, six to Ensifer medicae, two to Bradyrhizobium canariense, and one to Rhizobium radiobacter. Inoculation of host plants and analysis of the nodC genes revealed that most of them were symbiotically effective. Finally, three isolates were selected for bioremediation processes with restoration purposes on the basis of their levels of Hg tolerance, their response to high concentrations of this heavy metal, and their genetic affiliation and nodulation capacity.