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 costs remains a grand challenge. Here, we report a hybrid material of Co3O4 nanocrystals grown on reduced graphene oxide (GO) as a high-performance bi-functional catalyst for oxygen reduction reaction (ORR) and oxygen evolution reaction (OER). While 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.