In this study, the nano-spinel CoMn2O4 was synthesized by coprecipitation pyrolysis and employed to heterogeneously activate hypochlorite (NaClO) for the oxidative decolorization of methylene blue (MB). The crystal structure, elemental composition, surface morphology, and microstructure of the prepared CoMn2O4 nano-spinel were analyzed using a series of characterization techniques. The pyrolysis temperature was screened on the basis of MB decolorization efficiency and the leaching of metal ions during the reaction. The MB decolorization efficiency was compared using different catalysts and process. The impacts of CoMn2O4 dosage, effective chlorine dose, MB concentration, and initial pH on MB decolorization were explored. The catalytic mechanism of MB oxidation was elucidated through quenching experiments combined with radical identification. The degradation pathway of MB was preliminarily proposed based on the detection of the intermediates. The reusability of recycled CoMn2O4 was finally investigated. The results revealed that maximal MB oxidation efficiency and minimal leaching of Co and Mn ions were achieved at the calcination temperature of 600 °C. Complete oxidative decolorization of MB within 40 min was obtained at an initial MB concentration of 50 mg/L, a CoMn2O4 dosage of 1 g/L, an effective chlorine dose of 0.1%, and an initial pH of 4.3. Superoxide radical (O2•−) was found to be dominantly responsible for MB decolorization according to the results of radical scavenging experiments and electron paramagnetic resonance. The CoMn2O4 spinel can be recycled for five cycles with the MB removal in the range of 90.6~98.7%.