Composite electrodes represent an important class of electromaterials, with enhanced functional properties tailored for targeted applications. Introduction of graphene as a conductive nanofiller into the thermoplastic polyurethane (PU) provides electrodes with interesting properties. In this study, a highly conductive cathodically exfoliated graphene (CEG) of ∼2–8 μm lateral size was employed to prepare CEG-PU composites. The use of this larger graphene sheet requires loading of at least 20% w/w graphene to promote contact between the sheets, hence the conductivity. The CEG-PU composite electrodes were tested to determine their electrochemical capacitance and it was found that the 40% (w/w) CEG-PU composite shows areal capacitance, energy density, and power density of 2.51 mF/cm2, 1.56 μW/h/cm2, and 0.48 mW/cm2, respectively, at a current density of 0.2 mA/cm2 and an operating voltage of 1.0 V. In summary, the CEG-PU composite electrodes have excellent conductivity, chemical/mechanical properties, and capacitive performance.