The gut microbiome, often referred to as "super organ", comprises up to a hundred trillion microorganisms, and the species diversity may vary from person to person. They perform a decisive role in diverse biological functions related to metabolism, immunity and neurological responses. However, the microbiome is sensitive to environmental pollutants, especially heavy metals. There is continuous interaction between heavy metals and the microbiome. Heavy metal exposure retards the growth and changes the structure of the phyla involved in the gut microbiome. Meanwhile, the gut microbiome tries to detoxify the heavy metals by altering the physiological conditions, intestinal permeability, enhancing enzymes for metabolizing heavy metals. This review summarizes the effect of heavy metals in altering the gut microbiome, the mechanism by which gut microbiota detoxifies heavy metals, diseases developed due to heavy metal-induced dysbiosis of the gut microbiome, and the usage of probiotics along with advancements in developing improved recombinant probiotic strains for the remediation of heavy metal toxicity.