In this study, we, for the first time, demonstrate a general solid-phase pyrolysis method to synthesize hybrid transition metal nanocrystal-embedded graphitic carbon nitride nanosheets, namely M-CNNs, as a highly efficient oxygen electrocatalyst for rechargeable Zn-air batteries (ZABs). The ratios between metallic acetylacetonates and the g-C3N4 precursor can be controlled where Fe-CNNs-0.7, Ni-CNNs-0.7 and Co-NNs-0.7 composites have been optimized to exhibit superior ORR/OER bifunctional electrocatalytic activities. Specifically, Co-CNNs-0.7 exhibited not only a comparable half-wave potential (0.803 V vs. RHE) to that of the commercial Pt/C catalyst (0.832 V) with a larger current density for the ORR but also a lower overpotential (440 mV) toward the OER compared with the commercial IrO2 catalyst (460 mV), revealing impressive application in rechargeable ZABs. As a result, ZABs using Co-CNNs-0.7 as the cathode exhibited an excellent peak power density of 85.3 mW cm-2 with a specific capacity of 675.7 mA h g-1 and remarkable cycling stability of 1000 cycles, outperforming the commercially available Pt/C + IrO2 catalysts. This study highlights the synergy from heterointerfaces in oxygen electrocatalysis, thus providing a promising approach for advanced metal-air cathode materials.