Efficient and cost-effective bifunctional electrocatalysts for oxygen evolution reaction (OER) and oxygen reduction reaction (ORR) are of vital importance in energy conversion and storage devices. Despite the recent progress in bifunctional oxygen electrocatalysts, their unbalanced and insufficient OER and ORR activities has continued to pose challenges for the practical application of such energy devices. The design of highly integrated, high-performance, bifunctional oxygen electrocatalysts composed of highly graphitic nanoshells embedded in mesoporous carbon (GNS/MC) is reported. The GNS/MC exhibits very high oxygen electrode activity, which is one of the best performances among nonprecious metal bifunctional oxygen electrocatalysts, and substantially outperforms Ir- and Pt-based catalysts. Moreover, the GNS/MC shows excellent durability for both OER and ORR. In situ X-ray absorption spectroscopy and square wave voltammetry reveal the roles of residual Ni and Fe entities in enhancing OER and ORR activities. Raman spectra indicate highly graphitic, defect-rich nature of the GNS/MC, which can contribute to the enhanced OER activity and to high stability for the OER and ORR. In aqueous Na–air battery tests, the GNS/ MC air cathode-based cell exhibits superior performance to Ir/C- and Pt/C based batteries. Significantly, the GNS/MC-based cell demonstrates the first example of rechargeable aqueous Na–air battery.