Cobalt-based electrolytes have significantly advanced the tunability and performance of dye-sensitized solar cells. The typically used platinum cathodes are expensive and non-optimal for cobalt complexes, motivating the search for replacements. Graphene nanopowders are a viable alternative but they are mechanically unstable as catalysts due to their poor substrate adhesion. Here we report a new type of carbon-graphene nanocomposite that maintains the catalytic performance of graphene with enhanced adhesion via a conductive carbon matrix. These nanocomposites were synthesized by carbonizing mixtures of graphene nanoplatelets with a carbon-source, poly(acrylonitrile). The resulting materials had tunable performance with a low charge transfer resistance of similar to 1 Omega cm(2) using as little as 20% graphene. Dye-sensitized solar cells fabricated with these carbon-graphene nanocomposites had enhanced fill factors and enhanced power conversion efficiencies as compared to platinum cathodes. Accelerated mechanical aging led to the complete detachment of graphene-only electrodes whereas carbon-graphene nanocomposites were stable.