In this work, a low-cost, high-performance, and environmentally friendly non-precious-metal catalyst was fabricated via a simple pyrolysis of the corn starch, dicyandiamide, and cobalt acetate for the oxygen reduction reaction (ORR). Scanning electron microscope (SEM) and transmission electron microscopy (TEM) images show that the catalyst has porous and graphene-like carbon nanosheet-encased metal nanoparticles structure. Electrochemical measurements show that, compared to the commercial Pt/C catalysts, the catalyst has a low overpotential, larger current density, and better methanol tolerance ability for ORR in both alkaline and acidic media, which may be attributed to the incorporation of Co–Nx moieties and Co nanoparticles. The transferred number of electrons during the ORR with the catalyst was calculated to be ∼3.9 in alkaline media (∼3.7 in acidic media), indicating that the product would be a promising non-noble cathode catalyst in alkaline and acidic fuel cells or Li/Zn air batteries.