This paper reports the synthesis of Co3O4–reduced graphene oxide (rGO) hybrids and the catalytic performance in heterogeneous activation of peroxymonosulfate (PMS) for the decomposition of phenol. The surface morphologies and structures of the Co3O4–rGO hybrids were investigated by field emission scanning electron microscopy (SEM), energy-dispersive X-ray spectrometer (EDS), transmission electron microscopy (TEM), powder X-ray diffraction (XRD), Raman spectroscopy, Fourier transform infrared spectroscopy (FTIR), and thermogravimetric analysis (TGA). Through an in situ chemical deposition and reduction, Co3O4–rGO hybrids with Co3O4 nanoparticles at an average size of 33 nm were produced. Catalytic testing showed that 20 mg/L of phenol could be completely oxidized in 20 min at 25 °C on Co3O4–rGO hybrids, which is mostly attributed to the generation of sulfate radicals through Co3O4-mediated activation of PMS. Phenol oxidation was fitted by a pseudo-zero-order kinetic model. The rate constant was found to increase with increasing temperature and PMS dosage, but to decrease with increasing initial phenol concentration. The combination of Co3O4 nanoparticles with graphene sheets leads to much higher catalytic activity than pure Co3O4. rGO plays an important role in Co3O4 dispersion and decomposition of phenol.