The high cost and limited natural abundance of platinum hinder its widespread applications as the oxygen reduction reaction (ORR) electrocatalyst for fuel cells. Carbon-supported materials containing metals such as Fe or Co as well as nitrogen have been proposed to reduce the cost without obvious lowering the performance compared to Pt-based electrocatalysts. In this work, based on the pyrolyzed corrin structure of vitamin B12 on the simultaneously reduced graphene support (g-VB12), we construct an efficient oxygen reduction electrocatalyst with very positive half-wave potential (only ∼ 30 mV deviation from Pt/C), high selectivity (electron transfer number close to 4) and excellent durability (only 11 mV shift of the half-wave potential after 10,000 potential cycles). The admirable performance of this electrocatalyst can be attributed to the homogeneous distribution of abundant Co-Nx active sites, and a well-defined three-dimensional mesoporous structure of the N-doped graphene support. The high activity and long-term stability of the low cost g-VB12 make it a promising ORR electrocatalyst in alkaline fuel cells.