Graphene oxide/Fe3O4 (GO/Fe3O4) nanoparticles were synthesized by an ultrasonic-assisted reverse co-precipitation method, and then horseradish peroxidase (HRP) was covalently immobilized onto GO/Fe3O4 with 1-ethyl-3-(3-dimethyaminopropyl)carbodiimide (EDC) as a cross-linking agent. In order to enhance the phenol removal efficiency and prevent the inactivation of the enzyme, the polyethylene glycol with highly hydrophilicity was added in this reaction, because the adsorption capacity for the polymer by degradation was stronger than the HRP. The results showed that the immobilized enzyme removed over 95% of phenol from aqueous solution. The catalytic condition was extensively optimized among the range of pH, mass ratio of PEG/phenol as well as initial concentration of immobilized enzyme and H2O2. The HRP immobilized on GO/Fe3O4 composite could be easily separated under a magnetic field from the reaction solution and reused.