Olive cake, the solid byproduct of three-phase centrifugation olive oil production, has a high organic and polyphenol content, rendering it an environmental threat when landfilled as well as limiting its animal feed potential. This residue can be a good candidate for biomethane production due to its rich polysaccharide content (pectin, hemicellulose, and cellulose). Two strategies were compared to maximize biomethane production: destoning (i.e., removal of the seed fragments via mechanical means) and enzymatic pretreatment of the pulp. After 30 days of batch anaerobic digestion at 35 °C, both enzymatically pretreated and destoned olive cakes produced similar amounts of methane (~295 mL CH4/g volatile solids (VS)), 42% more than the control. A comparison of olive cake’s biomethane yields with a broad range of agricultural residues in the literature demonstrated its suitability for biomethane production. Additionally, the digestate recovered from the anaerobic digestion of olive cake had high Kjeldahl nitrogen contents (3.6%, db) and low polyphenol concentrations (0.02 mg gallic acid equivalent (GAE)/g), qualifying it as an ingredient for soil amendment. This study demonstrated olive cake can be diverted from landfills for second-generation biofuel production, and that the resulting digestate may have value for soil amendment.