Four different morphologies of nanostructured MnO2 (nanospheres, nanosheets, nanoflowers and nanonods) were fabricated on a carbon fiber paper (CFP) substrate using a facile method of anodic electrodeposition by varying the H2SO4 concentration and current density. The fabricated composite electrodes were characterized by field emission scanning electron microscopy (FESEM), X-ray diffraction (XRD) and electrochemical techniques. The composite electrodes with MnO2 nanosphere/CFP, MnO2 nanosheet/CFP, MnO2 nanoflower/CFP and MnO2 nanonod/CFP achieved a relatively high specific capacitance (areal capacitance) of 134.4 F g−1 (0.20 F cm−2), 226.3 F g−1 (0.33 F cm−2), 235.6 F g−1 (0.35 F cm−2) and 362.5 F g−1 (0.54 F cm−2) at 0.5 A g−1, respectively. When the GV charging-discharging rate increased from 0.5 to 5 A g−1, the MnO2 nanorod/CFP composite decreased from 362.5 F g−1 (0.54 F cm−2) to 160.0 F g−1 (0.24 F cm−2), which is a relatively high retention of the original capacitance (i.e., 44.1%). All the composite electrodes with various nanostructured MnO2 morphologies under flat and bent states retained more than 95% and 90% of the initial capacitance after 5000 cycles at 5 A g−1, respectively, which demonstrates outstanding cycling stability. This study provides a novel approach for high-performance, morphology-controllable metal oxide electrodes for supercapacitors.