A facile non-template solid-state reaction method has been developed for the first time preparation of a tetragonal microstructure self-assembled from nitrogen-doped carbon nanocapsules containing metallic cobalt nanoparticles (Co-N-C) by using graphitic carbon nitride (g-C3N4) and Co(CH3COO)2·4H2O as the only reactants, in which g-C3N4 acts as the effective source of nitrogen and carbon elements in the N-doped carbon nanocapsules and Co(CH3COO)2·4H2O controls the microscopic structure of the self-assembled product. The as-prepared Co-N-C tetragonal microstructures exhibit enhanced electrocatalytic activities for both the oxygen reduction reaction (ORR) and oxygen evolution reaction (OER). The synergistic effect of the chemical compositions and the robust microstructure made of the interconnected N-doped carbon nanocapsules accounts for the superior ORR and OER activity and stability to the commercial Pt/C electrocatalyst. The synthetic strategy presented in this work demonstrates a new avenue for developing highly active carbon-based electrocatalysts for electrochemical energy storage and conversion.