In the domain of energy storage, electrochemical capacitors have numerous applications ranging from hybrid vehicles to consumer electronics, with very high power density at the cost of relatively low energy storage. Here, we report an approach that uses vertically aligned carbon nanotube arrays as electrodes in electrochemical capacitors. Different electrolytes were used and multiple parameters of carbon nanotube array were compared: carbon nanotube arrays were shown to be two to three times better than graphite in term of specific capacitance, while the surface functionalization was demonstrated to be a critical factor in both aqueous and nonaqueous solutions to increase the specific capacitance. We found that a maximum energy density of 21 Wh/kg at a power density of 1.1 kW/kg for a hydrophilic electrode, could be easily achieved by using tetraethylammonium tetrafluoroborate in propylene carbonate. These are encouraging results in the path of energy-storage devices with both high energy density and power density, using only carbon-based materials for the electrodes with a very long lifetime, of tens of thousands of cycles.