Monodisperse Ce_1-xZr_xO₂ nanocrystals have been synthesized using a simple two-phase approach; adjusting the ratio of precursors used, amount of capping agent used, reaction time and temperature affords precise control over their composition, structure and size. Size-dependent enhancement of oxygen-storage capacity and kinetics of oxygen storage and release were observed. Systematic studies were conducted in order to understand the size-dependent enhancement of these properties. This work provides important insights into the synthesis and fundamental understanding of multi-component nanocrystals with a large variety of applications.