A new hierarchical approach is presented for elucidating the structural disorder in Ce1−xGdxO2−x/2 solid solutions on different scale lengths. The primary goal of this investigation is to shed light on the relations between the short-range and the average structure of these materials via an analysis of disorder on the mesocopic scale. Real-space (pair distribution function) and reciprocal-space (Rietveld refinement and microstructure probing) analysis of X-ray powder diffraction data and electron spin resonance (ESR) investigations were carried out following this approach. On the local scale, Gd- and Ce-rich droplets (i.e. small regions a few ångströms wide) form, exhibiting either a distorted fluorite (CeO2) or a C-type (Gd2O3) structure in the whole compositional range. These droplets can then form C-type nanodomains which, for Gd concentrations xGd ≤ 0.25, are embedded in the fluorite matrix. At the site percolation threshold pC for a cubic lattice (xGd = pC ≃ 0.311), C-type nanodomains percolate inside each crystallite and a structural phase transformation is observed. When this occurs, the peak-to-peak ESR line width ΔHpp shows a step-like behaviour, which can be associated with the increase in Gd–Gd dipolar interactions. A general crystallographic rationale is presented to explain the fluorite-to-C-type phase transformation. The approach shown here could be adopted more generally in the analysis of disorder in other highly doped materials.