We report on the development of highly conductive NiCo2S4 single crystalline nanotube arrays grown on a flexible carbon fiber paper (CFP), which can serve not only as a good pseudocapacitive material but also as a three-dimensional (3D) conductive scaffold for loading additional electroactive materials. The resulting pseudocapacitive electrode is found to be superior to that based on the sibling NiCo2O4 nanorod arrays, which are currently used in supercapacitor research due to the much higher electrical conductivity of NiCo2S4. A series of electroactive metal oxide materials, including Co x Ni1–x (OH)2, MnO2, and FeOOH, were deposited on the NiCo2S4 nanotube arrays by facile electrodeposition and their pseudocapacitive properties were explored. Remarkably, the as-formed Co x Ni1–x (OH)2/NiCo2S4 nanotube array electrodes showed the highest discharge areal capacitance (2.86 F cm–2 at 4 mA cm–2), good rate capability (still 2.41 F cm–2 at 20 mA cm–2), and excellent cycling stability (∼4% loss after the repetitive 2000 cycles at a charge–discharge current density of 10 mA cm–2).