A facile and efficient two-step procedure was developed for the fabrication of a high-performance and binder-free cobalt oxide–carbon nanotubes (CO/CNT) pseudocapacitive electrode. First, CNTs were deposited on the surface of a chemically activated graphite sheet by cathodic electrophoretic deposition technique from their ethanolic suspension. In the next step, a thin film of cobalt oxide was electrodeposited on the CNTs coated graphite substrate by a galvanostatic method, followed by a thermal treatment in air. The structure and morphology of the prepared cobaltite electrode with and without CNT interlayer were characterized by X-ray diffraction (XRD), field emission scanning electron microscopy (FESEM) and nitrogen adsorption–desorption measurement. The results indicated that Co3O4 nanoparticles were uniformly attached on the surface of CNTs, to form a porous-structured CO/CNT composite electrode with a high specific surface area of 144.9 m2 g−1. Owing to the superior electrical conductivity of CNTs, high surface area and open porous structure, and improved integrity of the electrode structure, the composite electrode delivered a high areal capacitance of 4.96F cm−2 at a current density of 2 mA cm−2, a superior rate performance (64.7% capacitance retention from 2 mA cm−2 to 50 mA cm−2), as well as excellent cycling stability (91.8% capacitance retention after 2000 cycles), which are higher than those of the pure cobaltite electrode.