Industrial wastewater containing heavy metals, such as Cd and Pb, must be treated prior to discharge to meet increasingly stringent discharge guidelines and to limit the impact of toxic metals on ecosystems and human health. The application of olivine particles is a natural mineral-based solution to treat heavy metal-laden wastewaters, but little is known about the efficiency and mechanism of metal removal by this solid phase. In this work, we investigate the potential of olivine for heavy metal treatment by combining batch metal removal experiments with solid-phase characterization by synchrotron-based X-ray techniques and electron microscopy. We probed the removal behaviour of a variety of metal contaminants (Co, Ni, Cd, Zn, Cu, Pb; initial concentration = 1500 µg/L) and used Zn specifically to identify the metal removal pathway of olivine. We found that olivine in powdered (0.3 g/L) and granulated (0.5 g/L) forms was able to remove up to >90% of the initial metal, depending on the metal identity, with the efficiency increasing in order of Co ≤ Cd ≤ Ni <Zn<Cu<Pb. This order matches the well documented selectivity sequence of other common mineral sorbents (e.g., Fe(III) and Mn(IV) (oxyhydr)oxides). In addition, metal removal was intimately linked to increases in pH during reaction (e.g., from pH 7 to 10), due presumably to H+ consumption by SiO44− ions released during olivine dissolution. Molecular-scale characterization of the solid reaction products revealed that metal removal occurred via secondary precipitation of distinct metal carbonates and silicates, which was promoted by the increase in pH, although metal adsorption to olivine surfaces might also occur at lower pH. Overall, our study provides strong evidence for the potential of olivine minerals for treatment of heavy metal-laden industrial wastewaters.