Anaerobic digestion technology can play a significant role in the transition to a low-carbon and circular economy by producing bioenergy (biomethane) and organic fertilizer (digestate). This study proposes a valorization approach for three waste streams widely produced in the Mediterranean area: fish waste (FW), pig slurry (PS), and orange pomace (OP). The FW lipid content can enhance biomethane yield as long as inhibition by long-chain fatty acids is prevented. In this study, the effect of introducing 25% and 50% FW to the anaerobic co-digestion of a reference mixture consisting of 80% PS and 20% OP pulp (OPP) was studied. Co-digestion using 50% FW presented the maximum biomethane yield (669.68 ± 8.32 mL CH4/g VSadded), which corresponds to a 37% increase compared to the reference. No inhibition was detected during the anaerobic digestion assay. The kinetic study showed that the introduction of FW led to a reduction in the degradation rate constant by up to 30%. The lag phase increased as FW content increased, with 50% FW presenting a lag time approximately three times that of the reference mixture. The proposed strategy can encourage sustainable waste management practices and contribute to GHG emissions mitigation.