A simple and scalable method has been developed to fabricate nanostructured MnO2-carbon nanotube (CNT)-sponge hybrid electrodes. A novel supercapacitor, henceforth referred to as "sponge supercapacitor", has been fabricated using these hybrid electrodes with remarkable performance. A specific capacitance of 1,230 F/g (based on the mass of MnO2) can be reached. Capacitors based on CNT-sponge substrates (without MnO2) can be operated even under a high scan rate of 200 V/s, and they exhibit outstanding cycle performance with only 2% degradation after 100,000 cycles under a scan rate of 10 V/s. The MnO2-CNT-sponge supercapacitors show only 4% of degradation after 10,000 cycles at a charge-discharge specific current of 5 A/g. The specific power and energy of the MnO2-CNT-sponge supercapacitors are high with values of 63 kW/kg and 31 Wh/kg, respectively. The attractive performances exhibited by these sponge supercapacitors make them potentially promising candidates for future energy storage systems.