Polymer-derived Si–O–C ceramics using Yttria Stabilised Zirconia (YSZ) as structural material reinforced by homogenously distributed graphene using CTAB as surfactant were synthesized using gel casting process, cross-linking and sintering. The microstructure and mechanical properties of the graphene reinforced YSZ based ceramic composites have been investigated. Scanning Electron Microscopy (SEM) examinations confirm homogenous distribution of graphene on the fracture surfaces of the sintered composite. Incorporation of small amounts of graphene leads to remarkable mechanical properties improvement in our composites. In particular, the indentation fracture toughness and hardness are 20.31% and 25.78% over monolithic YSZ with maximum values of 4.62 MPa1/2 and 16.6 GPa, respectively. The results show that graphene in ceramic composites lead to toughening of the composites through a range of toughening mechanisms, including graphene pull-out, crack bridging and crack deflection. This study has improved upon existing syntheses methods resulting in the use of lowered costs dispersant for graphene, increase in quality of graphene dispersion within ceramic matrix, remarkable increase in mechanical properties using the new generation ceramic material, YSZ and an environmentally friendly approach of fabricating YSZ–graphene ceramic composite.