Developing low cost oxygen reduction catalysts that perform with high efficiency is highly desirable for the commercial success of environmentally friendly energy conversion devices such as fuel cells and metal–air batteries. In this work a three-dimensional, 3D, self-assembled Mn3O4 hierarchical network has been grown on nitrogen doped reduced graphene oxide (NrGO), by a facile and controllable electrodeposition process and its electrocatalytic performance for oxygen reduction reaction (ORR) has been assessed. The directly electrodeposited MnOx on a glassy carbon electrode (GCE) exhibits little electrocatalytic activity, whereas the integrated Mn3O4/NrGO catalyst is more ORR active than the NrGO. The resulting electrode architecture exhibits an “apparent” four-electron oxygen reduction pathway involving a dual site reduction mechanism due to the synergetic effect between Mn3O4 and NrGO. The 3D Mn3O4/NrGO hierarchical architecture exhibits improved durability and methanol tolerance, far exceeding the commercial Pt/C. The enhanced ORR performance of the room temperature electrodeposited Mn3O4 nanoflake network integrated with NrGO reported here offers a new pathway for designing advanced catalysts for energy conversion and storage.