This study presents an investigation on the effect of heavy metals on the production of biogas during the process of anaerobic digestion (AD) of olive mill waste (OMW). The poisonous effect and the inhibitory influence of Fe, Ni, Pb, Zn, Cu, and Cr on the digestion process are investigated and determined. Biomethanation potential tests are performed for this sake. Adding some of the heavy metals to the AD decreases the efficiency of biogas production and methane concentration and decreases the reduction in the VS, the TCOD, the SCOD, and the organic acid load. A critical increase in the total organic acid and inhibition of methanogenic bacteria was observed due to its toxicity. The toxicity of the heavy metals can be arranged according to increasing order: Cu > Ni > Pb > Cr > Zn > Fe, which leads to rapid poisoning of the active microorganisms. Iron may also exhibit stimulatory effects, but with a low rate and at a certain level. The conclusions of this work are important for the industry and help to understand how to carefully manage the presence of heavy metals in the digestate.