Local populations of the pasture legumes Astragalus hamosus, Lotus edulis, Lotus ornithopodioides, Medicago ciliaris and Scorpiurus muricatus from heavy metal polluted and unpolluted sites in Sardinia were compared for tolerance to Zn, Cd and Pb in hydroponics. Tolerance of plants to heavy metals varied significantly depending on the species, origin of the population and metal. The species L. edulis, L. ornithopodioides and M. ciliaris possessed higher metal tolerance and were used in a pot experiment with Zn, Cd and Pb polluted mine waste. Seeds were inoculated with the metal tolerant plant growth-promoting rhizobacterium Variovorax paradoxus 5C-2 or/and with the corresponding symbiotic nodule bacteria containing the enzyme 1-aminocyclopropane-1-carboxylate deaminase. Co-inoculation with the bacteria had synergistic and additive effects on nodule number, root growth and uptake of elements (N, P, Ca, Mg, Na, Mn, Zn and Pb) in shoots of L. edulis and L. ornithopodioides. Shoot biomass and uptake of K, Fe and Cd was increased by a combined inoculation of L. edulis. The ratio between shoot and root contents of Pb in L. ornithopodioides was above 1, suggesting a characteristic trait of hyperaccumulating species. The results suggest that the development of metal tolerant and efficient plant-bacteria systems might be useful for phytostabilization and revegetation of mine wastes.