We demonstrate a facile fabrication scheme for Co3O4@CoO@Co (gradient core@shell) nanoparticles on graphene and explore their electrocatalytic potentials for an oxygen evolution reaction (OER) and an oxygen reduction reaction (ORR) in alkaline electrolytes. The synthetic approach begins with the preparation of Co3O4 nanoparticles via a hydrothermal process, which is followed by a controlled hydrogen reduction treatment to render nanoparticles with radial constituents of Co3O4/CoO/Co (inside/outside). X-ray diffraction patterns confirm the formation of crystalline Co3O4 nanoparticles, and their gradual transformation to cubic CoO and fcc Co on the surface. Images from transmission electron microscope reveal a core@shell microstructure. These Co3O4@CoO@Co nanoparticles show impressive activities and durability for OER. For ORR electrocatalysis, the Co3O4@CoO@Co nanoparticles are subjected to a galvanic displacement reaction in which the surface Co atoms undergo oxidative dissolution for the reduction of Pt ions from the electrolyte to form Co3O4@Pt nanoparticles. With commercial Pt/C as a benchmark, we determine the ORR activities in sequence of Pt/C > Co3O4@Pt > Co3O4. Measurements from a rotation disk electrode at various rotation speeds indicate a 4-electron transfer path for Co3O4@Pt. In addition, the specific activity of Co3O4@Pt is more than two times greater than that of Pt/C.