The mats of yttria-stabilized tetragonal zirconia nanofibers were prepared using electrospinning. The effect of calcination temperature in the range of 600–1200 °C on their microstructure, phase composition and mechanical properties was investigated. Phase composition of the nanofibers did not change in all ranges of the calcination temperatures, while the average grain size increased from 8 to 39 nm. Nanoindentation testing of the mats showed a decrease in the hysteresis loop energy in samples with higher calcination temperature. Hardness and the elastic modulus measured with the indentation technique were the highest for the mats calcined at 900 °C.