Mesoporous cobalt oxide (Co3O4) nanosheet electrode arrays are directly grown over flexible carbon paper substrates using an economical and scalable two-step process for supercapacitor applications. The interconnected nanosheet arrays form a three-dimensional network with exceptional supercapacitor performance in standard two electrode configuration. Dramatic improvement in the rate capacity of the Co3O4 nanosheets is achieved by electrodeposition of nanocrystalline, hydrous RuO2 nanoparticles dispersed on the Co3O4 nanosheets. An optimum RuO2 electrodeposition time is found to result in the best supercapacitor performance, where the controlled morphology of the electrode provides a balance between good conductivity and efficient electrolyte access to the RuO2 nanoparticles. An excellent specific capacitance of 905 F/g at 1 A/g is obtained, and a nearly constant rate performance of 78% is achieved at current density ranging from 1 to 40 A/g. The sample could retain more than 96% of its maximum capacitance even after 5000 continuous charge-discharge cycles at a constant high current density of 10 A/g. Thicker RuO2 coating, while maintaining good conductivity, results in agglomeration, decreasing electrolyte access to active material and hence the capacitive performance.