Inspired by the high specific capacitances found using ultrathin films or nanoparticles of manganese oxides (MnOx), we have electrodeposited MnOx nanoparticles onto sheets of carbon nanotubes (CNT sheets). The resulting composites have high specific capacitances (Csp <= 1250 F/g), high charge/discharge rate capabilities, and excellent cyclic stability. Both the Csp and rate capabilities are controlled by the average size of the MnOx nanoparticles on the CNTs. They are independent of the number of layers of CNT sheets used to form an electrode. The high-performance composites result from a synergistic combination of large surface area and good electron-transport capabilities of the MnOx nanoparticles with the good conductivity of the CNT sheets. Such composites can be used as electrodes for lithium batteries and supercapacitors.