CNT/Ni hybrid nanostructured arrays (NSAs) are synthesized on a stainless steel substrate through a one-step chemical-vapor-deposition (CVD) method using nullaginite NSAs as starting materials. During the CVD process, the nullaginite NSAs are transformed into Ni NSAs, which can further act as the catalysts to initiate the simultaneous in situ growth of CNTs on their surface, leading to an intriguing three-dimensional (3D) hybrid nanostructure. The resulting ordered CNT/Ni NSAs are highly porous and conductive, which are believed to be quite favorable for electrochemical applications. As a proof-of-concept demonstration of the functions of such a well-designed architecture in energy storage, the CNT/Ni NSAs are tested as the working electrodes of electrochemical capacitors (ECs). After being activated, the composite electrode exhibits both well-defined pseudo-capacitive and electrical double-layer behavior with high areal capacitance (up to 0.901 F cm−2), excellent cyclability (nearly 100% capacitance retention after 5000 cycles), and outstanding rate capability. The unique interconnected hybrid structure and virtues inherited from the conductive CNT network and porous NSAs are believed to be responsible for the excellent performance.