Mining-related lead (Pb) pollution of the soil poses serious hazards to ecosystems and living organisms, including humans. Improved heavy metal phytoremediation efficacy, achieved by using phytostabilizing plants assisted by plant-growth-promoting (PGP) microorganisms, has been presented as an effective strategy for remediating polluted soils. The objective of this research was to examine the response and potential of the plant-growth-promoting bacterium LMR356, a Rhodococcus qingshengii strain isolated from an abandoned mining soil, under lead stress conditions. Compared to non-contaminated culture media, the presence of lead induced a significant decrease in auxin production (from 21.17 to 2.65 µg mL-1) and phosphate solubilization (from 33.60 to 8.22 mg L-1), whereas other PGP traits increased drastically, such as 1-aminocyclopropane-1-carboxylic acid (ACC) deaminase activity (from 38.17 to 71.37 nmol mg-1 h-1 α-ketobutyrate), siderophore production (from 69 to 83%), exopolysaccharide production (from 1952.28 to 3637.72 mg mL-1), biofilm formation, and motility. We, therefore, investigated the behavior of Sulla spinosissima L. in the presence or absence of this strain under a variety of experimental conditions. Under hydroponic conditions, Sulla plants showed endurance to varying lead concentrations (500-1000 µM). Inoculation of plants with Rhodococcus qingshengii strain LMR356 enhanced plant tolerance, as demonstrated by the increase in plant biomass (ranging from 14.41 to 79.12%) compared to non-inoculated Pb-stressed and non-stressed control plants. Antioxidant enzyme activities (increasing by -42.71 to 126.8%) and chlorophyll (383.33%) and carotenoid (613.04%) content were also augmented. In addition to its impact on plant lead tolerance, strain LMR356 showed a growth-promoting effect on Sulla plants when cultivated in sterilized non-contaminated sand. Parameters such as plant biomass (16.57%), chlorophyll (24.14%), and carotenoid (30%) contents, as well as ascorbate peroxidase (APX), peroxidase (POD), and catalase (CAT) activities, were all elevated compared to non-inoculated plants. Furthermore, when the same plant species was cultivated in highly polluted soil, inoculation increased plant biomass and improved its physiological properties. These findings demonstrate that LMR356 is a phytobeneficial bacterial strain capable of enhancing Sulla growth under normal conditions and improving its heavy metal tolerance in multi-polluted soils. Thus, it can be considered a promising biofertilizer candidate for growing Sulla spinosissima L. or other selected plants intended for application in restoration and stabilization initiatives aimed at reviving and safeguarding environmentally compromised and polluted soils after mining activities.