We have reported the fabrication of flexible graphene-paper electrode (GPE) with a flat surface, whose internal structure has been formed with gradient porous build-up (from the surface to the 2-hydroxyethyl cellulose (HC)-coated paper). HC solution was used as a binder to form the gradient porous graphene layer, enabling it to create an anchoring force between the porous graphene layer and the filter paper. The morphology of GPE was investigated using a scanning electron microscope, and the surface resistance of the GPE as a function of graphene content was determined using four-probe method. The electrochemical performance of the GPE was evaluated using a three-electrode test cell by cyclic voltammetry. The gravimetric capacitance of GPE was found to be 120 F per gram of graphene, and the capacitance retention was within ca. 96% for over 500 cycles. This could be attributed to both the low surface resistance resulting from the flat surface and the high electrochemical activity caused by the gradient porous structure. This unique structure not only offers an enhanced conductivity and good electrical contact between the electrode and electrolyte but also helps GPE to maintain good cyclic stability, proving its potential for use in various rechargeable and portable energy-storage devices.