Cerium oxide nanoparticles (CeO2 NPs) were fabricated and grown on graphene sheets using a facile, low cost hydrothermal approach and subsequently characterized using different standard characterization techniques. X-ray photoelectron spectroscopy and electron paramagnetic resonance revealed the changes in surface states, composition, changes in Ce4+ to Ce3+ ratio, and other defects. Transmission electron microscopy (TEM) and high resolution TEM revealed that the fabricated CeO2 NPs to be spherical with particle size of ~10–12 nm. Combination of defects in CeO2 NPs with optimal amount of two-dimensional graphene sheets had a significant effect on the properties of the resulting hybrid CeO2-Graphene nanostructures, such as improved optical, photocatalytic, and photocapacitive performance. The excellent photocatalytic degradation performances were examined by monitoring their ability to degrade Congo red ~94.5% and methylene blue dye ~98% under visible light irradiation. The photoelectrode performance had a maximum photocapacitance of 177.54 Fg−1 and exhibited regular capacitive behavior. Therefore, the Ce3+-ion, surface-oxygen-vacancies, and defects-induced behavior can be attributed to the suppression of the recombination of photo-generated electron–hole pairs due to the rapid charge transfer between the CeO2 NPs and graphene sheets. These findings will have a profound effect on the use of CeO2-Graphene nanostructures for future energy and environment-related applications.