Calcia-stabilized zirconia powders with a mean crystallite size of 5–20 nm and different calcia contents were prepared by colloidal high-energy ball milling of naturally occurring zirconia (baddeleyite) in water. Pellet-shaped green bodies were prepared by uniaxial pressing of the milled powders. Ceramics with high tetragonal zirconia content of nearly full density were produced by sintering. Calcia content corresponding to high fraction of tetragonal phase was found to be within the 4–10 mol% range. The Vickers hardness of bulk ceramics increased from 7.55 GPa to 13.3 GPa with increasing calcia content in the 0–13 mol% range. The fracture toughness was shown to have maximum value of 13.3 MPa m0.5 at 6.6 mol% calcia concentration.