The potential of rhizobacteria in assisting plants used in the phytostabilization or re-vegetation of soils contaminated by heavy metals is gaining interest all around the world. In this context, six rhizobacterial strains isolated from highly heavy metal-contaminated soils situated in abandoned mining sites around the Oujda region (Morocco) were tested with Sulla spinosissima (L.), a native leguminous plant expanding in this area. The strains used were multi-resistant to heavy metals and possessed multiple plant growth-promoting traits. Potential beneficial effects of the strains were also evaluated in planta by measuring various growth and physiological parameters of inoculated Sulla plants grown in sterilized sand. Inoculation with the Rhodococcus qingshengii strain LMR340 boosted plant biomass (39% to 83% increase compared to uninoculated plants), chlorophyll and carotenoid content (up to 29%), and antioxidant enzyme activities (15% to 80% increase). Based on these interesting findings, selected strains were inoculated into plants growing in a heavy metal, multi-polluted, and poor soil. Under these conditions, non-inoculated plants and those inoculated with the strain LMR250 were unable to grow, while the other five bacterial inoculants restored plant growth. The best performing strain, Pseudarthrobacter oxydans LMR291, could be considered as a good biofertilizer and/or biostimulant candidate to be used for promoting the growth of selected plants in re-vegetation and/or phytostabilization programs of degraded and contaminated soils.