We have synthesized a metal-free composite ink that contains graphene dots (GDs) and poly(3,4-ethylenedioxythiophene):polystyrene sulfonate (PEDOT:PSS) that can be used on paper to serve as the counter electrode in a flexible dye-sensitized solar cell (DSSC). This paper-based GD/PEDOT:PSS electrode is low-cost, light-weight, flexible, environmentally friendly, and easy to cut and process for device fabrication. We determined the GD/PEDOT:PSS composite effectively fills the dense micro-pores in the paper substrate, which leads to improved carrier transport in the electrode and a 3-fold enhanced cell efficiency as compared to the paper electrode made with sputtered Pt. Moreover, the DSSC with the paper electrode featuring the GD/PEDOT:PSS composite did not fail in photovoltaic tests even after bending the electrode 150 times, whereas the device made with the Pt-based paper electrode decreased in efficiency by 45% after such manipulation. These exceptional properties make the metal-free GD/PEDOT:PSS composite ink a promising electrode material for a wide variety of flexible electronic applications.