We report on the mechanical and structural properties of nanocrystalline 8% and 10% mol yttria stabilized zirconia (YSZ) obtained using mechanical alloying (MA). For milling times above 32 hours the complete alloying of the starting Y2O3 and ZrO2 powders is achieved. The asmilled powders show a body-centered cubic crystalline structure with grain sizes in the order of 10 nm. After uniaxial pressing and sintering the compacts exhibit densities of more than 93% of the theoretical value. The microhardness of the compacts increases with sintering temperature, reaching a maximum value of 913 HV0.5 after sintering at 1220º C for 6 hours. The correlation of these enhanced mechanical properties with the microstructural changes induced by heat treatment of the nanocrystalline MA powders is discussed.