Catalytic activity is primarily a surface phenomenon, however, little is known about Co3O4 nanocrystals in terms of the relationship between the oxygen reduction reaction (ORR) catalytic activity and surface structure, especially when dispersed on a highly conducting support to improve the electrical conductivity and so to enhance the catalytic activity. Herein, we report a controllable synthesis of Co3O4 nanorods (NR), nanocubes (NC) and nano-octahedrons (OC) with the different exposed nanocrystalline surfaces ({110}, {100}, and {111}), uniformly anchored on graphene sheets, which has allowed us to investigate the effects of the surface structure on the ORR activity. Results show that the catalytically active sites for ORR should be the surface Co(2+) ions, whereas the surface Co(3+) ions catalyze CO oxidation, and the catalytic ability is closely related to the density of the catalytically active sites. These results underscore the importance of morphological control in the design of highly efficient ORR catalysts.