Graphene nano-walls (GNWs) are promising materials that can be used as an electrode in electrochemical devices. We have grown GNWs by inductively-coupled plasma-enhanced chemical vapor deposition on stainless steel (AISI304) substrate. In order to enhance the super-capacitive properties of the electrodes, we have deposited a thin layer of MnO2 by electrodeposition method. We studied the effect of annealing temperature on the electrochemical properties of the samples between 70 °C and 600 °C. Best performance for supercapacitor applications was obtained after annealing at 70 °C with a specific capacitance of 104 F·g−1 at 150 mV·s−1 and a cycling stability of more than 14k cycles with excellent coulombic efficiency and 73% capacitance retention. Electrochemical impedance spectroscopy, cyclic voltammetry, and galvanostatic charge/discharge measurements reveal fast proton diffusion (1.3 × 10−13 cm2·s−1) and surface redox reaction after annealing at 70 °C.