Soil metal contamination is a major concern due to the ever-rising number of areas afflicted worldwide and the detrimental effects of metals to the environment and human health. Due to their non-biodegradability and toxicity, it is paramount to prevent further metal contamination and remediate the thousands of contaminated sites across the planet. Yet, conventional reclamation based on physical and chemical methods is often expensive, impractical, and triggers secondary pollution issues. Hence, microbe-aided phytoremediation has been gaining significant traction due to its environment-friendly character, cost-effectiveness, and the breakthroughs achieved during the past few decades. Microorganisms are an essential part of natural ecosystems and play a crucial role in their restoration. Indeed, plant-microbe associations in metal-polluted soils are pivotal for plants to tolerate metal toxicity and thrive in these harsh environments. Therefore, improving the understanding of this intricate relationship is invaluable for boosting phytoremediation. In this review, we focus on the potential of plant growth promoting bacteria (PGPB) for enhancing phytoremediation of metal-polluted soils. We discuss the mechanisms employed by microbes to promote plant growth and assist the removal or immobilization of metals in soil, thereby enhancing phytoextraction and phytostabilization, respectively. Microbe-mediated metal removal and detoxification through processes entailing adsorption, chelation, transformation, and precipitation, to list but a few, are also critically examined. Moreover, this work covers the direct and indirect mechanisms used by PGPB to facilitate plant acquisition of nutrients like nitrogen and phosphorus, supply and regulate phytohormones, and exert control over antagonistic microorganisms. Lastly, we provide an outlook on the future directions of microbe-aided phytoremediation and phytomining. Clearly, to fully validate and comprehend the potential of PGPB-aided phytoremediation, a considerable shift from bench-scale to field research is necessary. What's more, it is envisaged that recent advancements in genetic engineering may soon help furthering the efficiency of microbe-assisted phytoremediation.