Nanocrystalline powders of Ce0.5Zr0.5O2 were synthesized and characterized for the application as a catalyst support and oxygen storage medium in automotive catalysis. Detailed pair-distribution function analysis of the neutron diffraction data revealed an unusual structure of the nanocrystallites, consisting of domains of Ce0.4Zr0.6O2 composition of similar to25-30 Angstrom in size in a matrix of Ce0.7Zr0.3O2. The domains cannot be detected by conventional diffraction analysis because the crystallographic structure and orientation of the atomic planes are the same for all ceria- and zirconia-enriched regions within the crystallite, which therefore gives rise to Bragg scattering as a whole. The oxygen storage capacity did not show a correlation with either crystallite size or surface area of the samples. We suggest that the smaller size of zirconia-enriched domains associated with larger interfacial area between ceria- and zirconia-enriched regions is responsible for the increase in oxygen storage capacity.