The real structure of nanocrystalline CeO2-ZrO2 (Ce:Zr=1:1) systems prepared via the polymerized polyester precursor (Pechini) route and doped with La3+ or Gd3+ cations, up to 30 at.%, was studied by X-ray powder diffraction, EXAFS and Raman spectroscopy and the surface features characterized by XPS and SIMS. Undoped CeO2-ZrO2 system revealed nanoscale heterogeneity, perhaps due to the co-existence of Zr- or Ce-enriched domains. With large La3+ dopant the system remains bi-phasic within the studied ranges of composition, incorporation of the smaller Gd3+ cation stabilizes the single-phase solid solution. For both systems, the increase of dopant content was accompanied by a decline of domain size and an increase of the average lattice parameter of fluorite-like phases. Depletion of the surface layer by smaller Zr4+ cations was observed, while the surface content of a doping cation is either, close to that in the bulk (La) or below it (Gd). Such a spatial distribution of components results in some ordering of cations within the lattice. It is reflected in different modes of rearrangement of oxygen coordination polyhedra with the Gd or La content (distances and coordination numbers by EXAFS), and specificity of XRD patterns not conforming to a simple model with statistical distribution of oxygen vacancies.