We herein report a simple two-step procedure for fabricating tetragonal CoMn2O4 spinel nanocrystals on carbon fibers. The battery-type behavior of these composite fibers arises from the redox activity of CoMn2O4 in an alkaline aqueous solution, which, in combination with the carbon fibers, endows good electrochemical performance and long-term stability. The C@CoMn2O4 electrode exhibited high specific capacity, up to 62 mA h g-1 at 1 A g-1 with a capacity retention of around 90% after 4000 cycles. A symmetrical coin-cell device assembled with the composite electrodes delivered a high energy density of 7.3 W h kg-1 at a power density of 0.1 kW kg-1, which is around 13 times higher than that of bare carbon electrodes. The coin cell was cycled for 5000 cycles with 96.3% capacitance retention, at a voltage of up to 0.8 V, demonstrating excellent cycling stability.