Total x-ray diffraction and atomic pair distribution function analysis have been used to determine the atomic ordering in nanocrystalline (∼1.5nm in size) CeO2-ZrO2 prepared by a sol-gel route. Experimental data show that the oxides are a structurally and chemically inhomogeneous mixture of nanoscale domains with cubic-type and monoclinic-type atomic ordering, predominantly occupied by Ce and Zr atomic species, respectively. The study is another demonstration of the great potential of non-traditional crystallography in studying the structure of nanocrystalline materials. © 2007 IOP Publishing Ltd.