CeVO₄-rGO nanocomposites with varying proportions of CeVO₄: rGO (10, 20 and 30 wt% CeVO₄) were synthesized by a rapid microwave hydrothermal method. The prepared samples were characterized by X-ray powder diffraction (XRD), Fourier transform infrared (FTIR) spectroscopy, scanning/transmission electron microscopy (SEM/TEM), X-ray photoelectron spectroscopy (XPS), UV-visible spectroscopy to evaluate their structural, morphological and optical properties respectively. Lowering band gaps of CeVO₄-rGO composites (∼ 2.15 eV) made the sample active for photodegradation of Bromophenol blue (BRB) and Eosin Yellow (EY) dyes under visible light. Among all, the sample with 20 wt% CeVO₄ was the most efficient and almost complete degradation of EY (60 mg/L) was achieved within 60 min with a catalyst dose of 0.4 g/L. In comparison, 91.6 % of BRB dye (20 mg/L) was degraded in 105 min. Recyclability study up to the fourth cycle showed that the composites are fairly stable for reuse.