Nitrogen-doped graphene/graphene-tube nanocomposites are prepared by a high-temperature approach using a newly designed cage-containing metal-organic framework (MOF) to template nitrogen/carbon (dicyandiamide) and iron precursors. The resulting N-Fe-MOF catalysts universally exhibit high oxygen reduction activity in acidic, alkaline, and non-aqueous electrolytes and superior cathode performance in Li-O2 batteries.