Biogas residues and coal fly ash composite (CFA/BRC) were first investigated as novel heterogeneous catalysts for strengthening electro-Fenton (EF) of real British gas/Lurgi coal gasification wastewater. The prepared CFA/BRC was characterized by different techniques, i.e., SEM, XRD, BET surface area, XRF, and ICP-AES. The results indicated that CFA/BRC significantly improved performance of pollutant removal in EF across a wide pH range with current density of 10 mA/cm² and catalyst dosage of 1.0 g/L, and the treated wastewater was more biodegradable than homogeneous EF. Meanwhile, CFA/BRC showed superior stability at successive 2,400-min runs, and leached concentrations of heavy metals were very low without the second pollutant. The change of concentrations of dissolved oxygen and electro-generated H₂O₂, and fluorescence test indicated that the novel catalyst could enhance H₂O₂ decomposition into more hydroxyl radicals, which was considered to be mainly responsible for the pollutant removal. And the results offered new insights into sustainable use of waste materials.