Plants and microbes coexist or compete for survival and their cohesive interactions play a vital role in adapting to metalliferous environments, and can thus be explored to improve microbe-assisted phytoremediation. Plant root exudates are useful nutrient and energy sources for soil microorganisms, with whom they establish intricate communication systems. Some beneficial bacteria and fungi, acting as plant growth promoting microorganisms (PGPMs), may alleviate metal phytotoxicity and stimulate plant growth indirectly via the induction of defense mechanisms against phytopathogens, and/or directly through the solubilization of mineral nutrients (nitrogen, phosphate, potassium, iron, etc.), production of plant growth promoting substances (e.g., phytohormones), and secretion of specific enzymes (e.g., 1-aminocyclopropane- 1-carboxylate deaminase). PGPM can also change metal bioavailability in soil through various mechanisms such as acidification, precipitation, chelation, complexation, and redox reactions. This review presents the recent advances and applications made hitherto in understanding the biochemical and molecular mechanisms of plant–microbe interactions and their role in the major processes involved in phytoremediation, such as heavy metal detoxification, mobilization, immobilization, transformation, transport, and distribution.