A hybrid nanostructure with partially reduced graphene oxide (rGO) and carbon nanofibers (CNFs) was fabricated and used as supercapacitor electrodes. A straightforward, environmentally friendly, and low-cost microwave-assisted reduction process was developed for the synthesis of rGO/CNF hybrid structures. The fabricated supercapacitor devices showed a specific capacitance of 95.3Fg(-1) and a superior long-term cycling stability. A capacitance retention of more than 97% after 11000 galvanostatic charge discharge cycles was obtained. These and other results reported in this paper indicate that high-rate, all-carbon, rGO/CNF hybrid nanostructures are highly promising supercapacitor electrode materials.