A novel micro/nano-composite, based on cobalt(II) tetranitrophthalocyanine (CoTNPc) grown on poly(sodium-p-styrenesulfonate) modified graphene (PGr), as a non-noble-metal catalyst for the oxygen reduction reaction (ORR), is fabricated by an in situ solvothermal synthesis method. The CoTNPc/PGr is characterized by scanning electron microscopy (SEM), transmission electron microscopy (TEM), ultraviolet-visible (UV-vis) absorption spectroscopy, Fourier transform infrared spectroscopy (FTIR) and X-ray photoelectron spectroscopy (XPS), respectively. The electrocatalytic activity of the CoTNPc/PGr composite toward the ORR is evaluated using cyclic voltammetry and linear sweep voltammetry methods. The CoTNPc/PGr composite exhibits an unexpected, surprisingly high ORR activity compared to CoTNPc or PGr. The onset potential for ORR on CoTNPc/PGr is found to be around −0.10 V vs. SCE in 0.1 M NaOH solution, which is 30 mV and 70 mV more positive than that on PGr and CoTNPc, respectively. The peak current density on CoTNPc/PGr is about 2 times than that on PGr and CoTNPc, respectively. Rotating disk electrode (RDE) measurements reveal that the ORR mechanism is nearly via a four-electron pathway on CoTNPc/PGr. The current density for ORR on CoTNPc/PGr still remains 69.9% of its initial value after chronoamperometric measurements for 24 h. Pt/C catalyst, on the other hand, only retains 13.3% of its initial current. The peak potential shifts slightly and current barely changes when 3 M methanol is added. The fabricated composite catalyst for ORR displays high activity, good stability and excellent tolerance to the crossover effect, which may be used as a promising Pt-free catalyst in alkaline direct methanol fuel cells (DMFCs).