In this work, a facile and scalable method to produce cellulose based flexible electrodes is introduced. Composite paper electrodes from recycled paper pulp and graphene oxide (GO) were fabricated by solvent casting at room temperature. Electrical conductivity and surface chemistry of the nanocomposite samples were tuned by chemical reduction of GO. Contact angle measurements showed a change in water droplet angle from 0° to 89° depending on the GO content and degree of reduction. Electrical measurements depicted high electrical conductivity with an ideal Ohmic behavior for the composite paper electrodes. Sheet resistance of the sample containing 4 wt% of reduced GO (rGO) was 1.649 × 103 Ω/□ which is 5 orders of magnitude higher than paper pulp. The obtained sheet resistance for the sample with 16 wt% rGO was remarkably high for cellulose based conductive electrode compared with previously reported data. Moreover, the sample containing only 0.5 wt% of rGO showed 40% higher modulus than the neat recycled paper in tension. The resultant nanocomposite can be introduced as a highly conductive and low cost flexible electrode.