The aim of this work was using the legume plant Anthyllis vulneraria L. (ecotype metallicolous) as a trap plant, in order to isolate metal-tolerant rhizobial strains from metal-contaminated soils from Morocco, with pollution indexes spanning three orders of magnitude. As bioindicator, soil bacterial density was inversely correlated to the pollution index. Forty-three bulk soil bacteria and sixty two bacteria from nodules were isolated. The resistance of bacteria from nodules to heavy metals was four to ten times higher than that of bulk soil bacteria, reaching high maximum tolerable concentrations for Cd (2 mM), Cu (2 mM), Pb (7 mM), and Zn (3 mM). Besides, some strains show multiple metal-tolerant abilities and great metal biosorption onto the bacterial surface. Amplification and restriction analysis of ribosomal 16S rDNA (ARDRA) and 16S ribosomal DNA (rDNA) sequencing were used to assess biodiversity and phylogenetic position among bacteria present in nodules. Our results suggest that a great diversity of non-rhizobial bacteria (alpha- and gamma-proteobacteria) colonize nodules of Anthyllis plants in contaminated soils. Taking together, our results evidence that, in polluted soils, rhizobia can be displaced by non-rhizobial (and hence, non-fixing) strains from nodules. Thus, the selection of metal-resistant rhizobia is a key step for using A. vulneraria symbioses for in situ phytoremediation.