A single-step solvothermal approach to prepare stabilized cubic zirconia (ZrO2) nanoparticles (NPs) and highly reduced graphene oxide (HRG) and ZrO2 nanocomposite (HRG@ZrO2) using benzyl alcohol as a solvent and stabilizing ligand is presented. The as-prepared ZrO2 NPs and the HRG@ZrO2 nanocomposite were characterized using transmission electron microscopy (TEM) and X-ray diffraction (XRD), which confirmed the formation of ultra-small, cubic phase ZrO2 NPs with particle sizes of ~2 nm in both reactions. Slight variation of reaction conditions, including temperature and amount of benzyl alcohol, significantly affected the size of resulting NPs. The presence of benzyl alcohol as a stabilizing agent on the surface of ZrO2 NPs was confirmed using various techniques such as ultraviolet-visible (UV-vis), Fourier-transform infrared (FT-IR), Raman and XPS spectroscopies and thermogravimetric analysis (TGA). Furthermore, a comparative electrochemical study of both as-prepared ZrO2 NPs and the HRG@ZrO2 nanocomposites is reported. The HRG@ZrO2 nanocomposite confirms electronic interactions between ZrO2 and HRG when compared their electrochemical studies with pure ZrO2 and HRG using cyclic voltammetry (CV).