Nanostructured fibrous composite electrodes are prepared by direct electrooxidation of an ortho-phenylenediamine (oPD) monomer on a carbon network based on single-walled carbon nanotubes (SWCNTs). This simple and rapid fabrication method leads to the formation of a nanofibrous composite electrode, where the poly(ortho-phenylenediamine) (PoPD) layer envelops a previously formed carbon network, which is prepared with various SWCNT/PoPD ratios. Excellent cycling stability for more than 10 000 cycles is achieved for SWCNT/PoPD (wt/wt ratio of 1 : 5) in an asymmetric two-electrode configuration (in which Zn is used as both reference and counter electrodes) with a specific capacitance of about 350 F g−1 (35 mF cm−2) at 7.3 A g−1 (0.73 mA cm−2) current density. This performance is about 3 times higher than that of the PoPD (110 F g−1) electrode and ∼30 times higher than that of the bare carbon network (12 F g−1). The improved performance of the nanocomposite compared to that of its pristine counterparts is ascribed to a synergistic effect between the SWCNTs and PoPD, enhanced electrical conductivity and the resulting open porous network structure allowing the easy access of electrolyte ions into the electrode. This device structure with a capacitor-type nanocomposite cathode can be of interest for use in micro energy storage devices and for systems employing other charge carriers.