Crystal and local structures (long- and short-range order, respectively) of four nanocrystalline zirconia-based solid solutions—ZrO2-6 and 16 mol % CaO and ZrO2-2.8 and 12 mol % Y2O3—synthesized by a pH-controlled nitrate-glycine gel-combustion process were studied. These materials were characterized by synchrotron X-ray diffraction (XRD) and extended X-ray absorption fine structure (EXAFS) spectroscopy. Our XRD results indicate that the solid solution with low CaO and Y2O3 contents (6 and 2.8 mol %, respectively) exhibit a tetragonal crystallographic lattice, and those with higher CaO and Y2O3 contents (16 and 12 mol %, respectively) have a cubic lattice. Moreover, our EXAFS study demonstrates that the tetragonal-to-cubic phase transitions, for increasing CaO and Y2O3 contents, are both related to variations in the local symmetry of the Zr–O first neighbor coordination sphere.