Nanostructured composite particles of nano- and submicron sizes were synthesized by a combination of sol-gel and sonochemical techniques. Their graphene content was 0.8-0.9 wt%. These layered particles consisted of graphene sheets in which zirconia nanocrystals were discretely incorporated. The synthesized powders were characterized using XRD, TEM, HRTEM, diffusion aerosol spectrometry and elemental analysis. A comparison of the compressibility modulus, limit values of linear section deformation and compressibility factor shows that the compressibility of the composite is difficult to achieve compared to that of pure zirconia, apparently, due to the low elasticity of graphene sheets. This journal is © The Royal Society of Chemistry.