The use of biomasses that result from the agriculture and food industries in removing heavy metals from wastewaters is attracting increasing interest. We present a joined potentiometric and cross polarization magic angle spinning (CP-MAS) carbon-13 (13C) nuclear magnetic resonance (NMR) study on the interaction of olive stones with copper(II), nickel(II), and cadmium(II). The potentiometric measurements allow both to distinguish two kind of basic sites in the olive stones and to postulate the coordination models for the three studied metals. The NMR spectral analysis allows the attribution of the different signals to the components of the olive stone matrix. A comparison of CP-MAS 13C NMR spectra of the samples after metal treatment suggests a specific complexation between metal ions and hydroxyl groups on guaiacyl and syringyl moieties.