Despite a high demand for green energy sources, low performance of solid oxide fuel cells (SOFC) hinders the potential for its practical application. Zirconia-graphene composites are promising candidates as solid electrolytes for SOFC enabling efficient heat transfer and effective ion charge carriers movement. Herein, we report the change in electrochemical behavior of spark plasma sintered zirconia-reduced graphene oxide (YSZ-rGO) composites. The conductivity is shown to be altered from fully ionic to mixed electronic-ionic mode upon a small amount of rGO addition. Mixture of freeze-dried nano-sized yttria stabilized cubic zirconia (YSZ) powder and microwave sintered reduced graphene oxide (rGO) was utilized for the fabrication of YSZ-rGO ceramic composites. According to SEM and EBSD data, addition of rGO resulted in a bi-modal grain size distribution. The material with 2 wt.% rGO has demonstrated a mixed electron-ion conductivity in a wide temperature range of 294–1073 K in thermal cycling experiments at oxygen partial pressure of 10⁻³–10⁻⁵ atm, where oxygen ion conductivity dominates over electronic one at elevated temperatures. The electrochemical stability of YSZ-2 wt.% rGO was tested by thermal cycling in nitrogen and argon atmospheres via impedance spectroscopy at 473–1073 K. The model to describe the conductivity evolution with temperature and thermal cycling has been suggested for the first time.