This paper reports the synthesis and characterization of an efficient anionic olive stone waste-based material as new ion-exchanger adsorbent. The olive stone waste was subjected to an alkaline pretreatment in order to enhance their reactivity towards maleic anhydride. The maleate-derived material MOS was characterized by FTIR, 13C NMR, TGA and DSC. The resulting sodium form of material NaMOS was subjected to batch experiments in order to evaluate its cadmium and lead removal efficiency. Adsorption experimental data showed a uniform and rapid process. Both Langmuir and Freundlich isotherm models were found to fit adequately the equilibrium isotherm data. The sorption capacities reached 240.96 mg Cd g−1 and 127.38 mg Pb g−1. The thermodynamic parameters showed that the process was exothermic and the adsorption occurred spontaneously. The desorption experiments show a quantitative recovery of the metal ions from NaMOS material.