Graphene-doped ceramic composites with mixed electronic-ionic conductivity are currently attracting attention for their application in electrochemical devices, in particular membranes for solid electrolyte fuel cells with no necessity to use the current collector. In this work, composites of the Y2O3-ZrO2 matrix with graphene-augmented γ-Al2O3 nanofibres (GAlN) were spark plasma sintered. The conductivity and electrical stability in cyclic experiments were tested using electrical impedance spectroscopy. Composites with 0.5 and 1 wt.% GAlN show high ionic conductivity of 10−2–10−3 S/cm at 773 K. Around 3 wt.% GAlN percolation threshold was achieved and a gradual increase of electronic conductivity from ~10−2 to 4 × 10−2 S/cm with an activation energy of 0.2 eV was observed from 298 to 773 K while ionic conductivity was maintained at elevated temperatures. The investigation of the evolution of conductivity was performed at 298–973 K. Besides, the composites with 1–3 wt.% of GAlN addition show a remarkable hardness of 14.9–15.8 GPa due to ZrC formation on the surfaces of the materials.