The fabrication of graphene nanostructures, with a variety of morphologies and densities of defective sites, can be a promising tool to tune their characteristics towards photocatalytic applications, without the need for external dopants. In this study, the impact of morphological properties in terms of the orientation and defect concentrations of graphene nanostructures is demonstrated to support the development of active photocatalytic sites across graphitic structures. Vertically-aligned graphene nanosheets were grown across carbon fibres via electron cyclotron resonance microwave plasma chemical vapour deposition, to yield a range of different wall densities and edge functionalities. The variation of growth conditions was correlated to the photocatalytic activity for the degradation of methylene blue dye under ultra-violet and visible light. The chemical state of oxygen content hybridized with nanosheets was studied by X-ray photoelectron spectroscopy and correlated to the growth conditions and photocatalytic performance. The fastest degradation rate of dye was found on the graphene samples which were grown at 800 °C for 240 min, with a kinetic constant of 46.6 × 10−4 min−1. Such performance has not been observed to date for any graphitic materials and is shown to be on the same order of performance as the conventional photocatalytic materials.