The conventional technique to fabricate high energy density supercapacitors is to use pseudocapacitive materials such as metal oxides, conducting polymers as supercapacitor electrodes. However, the fabrication process of such electrodes is often complex and they suffer from low power density and short cycle life due to their low electrical conductivity and mechanical fragility. An innovative approach has recently been developed with the introduction of a redox additives into the electrolyte to boost the capacitance. In this work, a couple of new stable and effective redox-mediated gel electrolytes have been prepared by doping FeCl2/FeCl3 and K3Fe(CN)6/K4Fe(CN)6 into polyvinyl alcohol (PVA), and high performance solid-state supercapacitors have been fabricated using light commercial nanotube paper electrodes and the prepared gel polymer as electrolyte and separator. Vertical graphene petals have been grown on the carbon nanotube paper to enhance the available surface area. During charge/discharge, the redox species in the electrolytes exchange electrons with the electrode while undergoing fast, reversible reactions which leads to high capacitance and low internal resistance. The devices are mechanically robust and exhibit high volumetric capacitance (based on the total device volume) due to their extremely low thickness. A comparison study has been performed for PVA-K3Fe(CN)6-K4Fe(CN)6 redox gel electrolyte and PVA-H2SO4 gel electrolyte devices. The redox electrolyte device shows a three-fold higher capacitance and superior charge/discharge stability. After 3000 cycles, its capacitance retention is 78% which is nominally smaller than the PVA-H2SO4 device (81%). In summary, the new redox-mediated gel electrolytes have been demonstrated as simple, scalable ingredients for achieving high energy density with minute penalty in cyclic stability.