In this work, we evaluated the ability of rhizobacteria isolated from a metal-contaminated site to produce plant growth-promoting substances, such as indole-3-acetic acid (IAA), ammonia, hydrogen cyanide, siderophores and extracellular enzymes, to solubilize phosphate and for 1-aminocyclopropane-1-carboxylate (ACC)-deaminase activity, while assessing their capacity to enhance Trifolium repens growth. The rhizobacteria that better performed were used as bioinoculants for plants grown in zinc- and cadmium-spiked soils. Rhizobacteria were inoculated onto white clover seedlings growing in 250 and 500 mg kg−1 of zinc and in 10 and 30 mg kg−1 of cadmium-spiked soils and plant traits determined. The available and exchangeable rhizosphere metal concentrations were analyzed. Twenty rhizobacteria stimulated white clover growth under axenic conditions. Overall, strains Rhodococcus erythropolis EC 34, Achromobacter sp. 1AP2 and Microbacterium sp. 3ZP2 increased clover biomass in the absence and in presence of metals; however, in soils with 250 mg kg−1 of zinc, bacterial inoculation did not enhance plant biomass. Biomass enhancement may be related to the multiple bacterial promoting traits, especially the production of high levels of IAA and siderophores and the activity of ACC-deaminase. To the best of our knowledge, this is the first study reporting the potential of R. erythropolis to increase plant growth in metal-contaminated soils. In general, strains Microbacterium sp. 3ZP2 and Arthrobacter sp. EC 10 enhanced the available and exchangeable metal concentrations in rhizosphere showing their potential to improve phytoremediation efficiency. This work clearly indicates that rhizobacteria are promising for the development of bioinoculants useful for phytoremediation of polluted soils.