In this research, cetyltetraethyl ammonium bromide template assisted microwave procedure was utilized to synthesize reduced graphene oxide-zirconia (rGO-ZrO2) nanocomposites by varying the rGO composition (1, 2, 5 and 10 wt%). The physico-chemical characteristics of the nanocomposites were studied using X-ray diffraction (XRD), Raman, differential scanning calorimetry (DSC), scanning electron microscopy (SEM), diffusive reflectance ultraviolet-visible (DRUV-vis), X-ray photoelectron spectroscopy (XPS) and N2-physisorption techniques. The results from XRD, Raman and DSC studies indicate that the increase in rGO concentration resulted in the delay in ZrO2 crystallization temperature and alteration of ZrO2 phase from monoclinic to tetragonal due to an effective incorporation of rGO nanosheets in ZrO2 structure. The rGO loading also have an influence in the morphology of nanocomposites, as sample with 10 wt% rGO possessed unique monolith like morphology with macro pores. All the nanocomposites were utilized as photocatalysts for degradation of crystal violet dye in visible light irradiation. The rGO-ZrO2 nanocomposites showed high reaction rates; the nanocomposite with 5 wt% rGO showed the superior photocatalytic performance as this sample possessed low band gap energy, high surface area, pore volume and presence of surface rGO-ZrO2 interactive species as well as the reactive –OH groups. In addition, the synthesized nanocomposites exhibited excellent recyclability for photocatalytic degradation.