Electrocatalysts for anode or cathode reactions are at the heart of electrochemical energy conversion and storage devices. Molecular design of carbon based nanomaterials may create the next generation electrochemical catalysts for broad applications. Herein, we present the synthesis of a three-dimensional (3D) nanostructure with a large surface area (784 m(2) g(-1)) composed of nitrogen doped (up to 8.6 at.%) holey graphene. The holey structure of graphene sheets (~25% of surface area is attributed to pores) engenders more exposed catalytic active edge sites. Nitrogen doping further improves catalytic activity, while the formation of the 3D porous nanostructure significantly reduces graphene nanosheet stacking and facilitates the diffusion of reactants/electrolytes. The three factors work together, leading to superb electrochemical catalytic activities for both hydrazine oxidation (its current generation ability is comparable to that of 10 wt% Pt-C catalyst) and oxygen reduction (its limiting current is comparable to that of 20 wt% Pt-C catalyst) with four-electron transfer processes and excellent durability.