The inoculation of plants with plant-growth-promoting rhizobacteria has become a priority in the phytoremediation of heavy-metal-contaminated soils. A total of 82 bacteria were isolated from Sulla coronaria root nodules cultivated on four soil samples differently contaminated by heavy metals. The phenotypic characterization of these isolates demonstrated an increased tolerance to cadmium reaching 4.1mM, and to other metals, including Zn, Cu and Ni. Polymerase Chain Reaction/Restriction Fragment Length Polymorphism (PCR/RFLP) analysis showed a large diversity represented by genera related to Agrobacterium sp., R. leguminosarum, Sinorhizobium sp., Pseudomonas sp., and Rhizobium sp. Their symbiotic effectiveness was evaluated by nodulation tests. Taking into consideration efficiency and cadmium tolerance, four isolates were chosen; their 16SrRNA gene sequence showed that they belonged to Pseudomonas sp. and the Rhizobium sullae. The selected consortium of soil bacteria had the ability to produce plant-growth-promoting substances such as indole acetic acid and siderophore. The intracellular Cd accumulation was enhanced by increasing the time of incubation of the four soil bacteria cultivated in a medium supplemented with 0.1mM Cd. The existence of a cadmium-resistant gene was confirmed by PCR. These results suggested that Sulla coronaria in symbiosis with the consortium of plant-growth-promoting rhizobacteria (PGPR) could be useful in the phytoremediation of cadmium-contaminated soils.