Nanostructured coatings are experiencing a rapid development in recent years due to their potential applications in a wide variety of technological areas. In order to improve the properties of thermal barrier coatings, nanostructured 8 wt% yttria partial stabilized zirconia coatings were deposited by air plasma spraying with reconstituted nanoparticles on titanium alloy substrates. For comparison, the conventional counterparts were also fabricated. Their microstructures were investigated by using transmission electron micrograph and scanning electron micrograph. Their mechanical behaviors were evaluated via Vickers microhardness test and tensile test. The results indicate that the nanostructured zirconia coatings with original nanostructure and columnar grains have higher microhardness and adhesive strength than the conventional counterparts. Both the nanostructured coating and the conventional coating exhibit a bimodal distribution of microhardness values, which are analyzed via Weibull statistics. This phenomenon is attributed to the presence of molten and non-molten parts in the coatings.