We report on the mechanical and structural properties of nanocrystalline 8% and 10% mol yttria stabilized zirconia (YSZ) obtained using mechanical alloying (MA). The as-milled powders show a body-centered cubic structure with grain sizes in the nanometer scale. After uniaxial pressing and sintering the compacts exhibit good mechanical properties. We discuss the correlation of these enhanced properties with the microstructural changes induced by heat treatment.