Catalysts for oxygen reduction and evolution reactions are at the heart of key renewable-energy technologies including fuel cells and water splitting. Despite tremendous efforts, developing oxygen electrode catalysts with high activity at low cost remains a great challenge. Here, we report a hybrid material consisting of Co3O4 nanocrystals grown on reduced graphene oxide as a high-performance bi-functional catalyst for the oxygen reduction reaction (ORR) and oxygen evolution reaction (OER). Although Co3O4 or graphene oxide alone has little catalytic activity, their hybrid exhibits an unexpected, surprisingly high ORR activity that is further enhanced by nitrogen doping of graphene. The Co3O4/N-doped graphene hybrid exhibits similar catalytic activity but superior stability to Pt in alkaline solutions. The same hybrid is also highly active for OER, making it a high-performance non-precious metal-based bi-catalyst for both ORR and OER. The unusual catalytic activity arises from synergetic chemical coupling effects between Co3O4 and graphene.