HVOF thermal spraying has been developed to deposit dense ceramic coatings with improved protective properties for various applications. Even though HVOF coatings are much denser as compared to ordinary plasma sprayed coatings, the coating properties are inferior as compared to bulk ceramics because of pores and microcracks, which influence adversely the coating properties, i.e. toughness, hardness and wear resistance. One strategy to improve the properties of the coatings is to decrease the grain size of the ceramic phase and to add toughening elements to the microstructure. Nanocrystalline coatings have been found to offer better thermal shock resistance, lower thermal conductivity and better wear resistance than their conventional counterparts. In this paper we describe the development of nanocrystalline ceramic composite coatings, where the grain size of ceramic has been decreased and a few percents of alloying element has been added in order to toughen the coating. Dense nanostructured alumina coatings alloyed with Ni and ZrO2 nanosized particles were manufactured by HVOF spraying by using HV2000 spray gun. Mechanical properties, especially elastic modulus and relative fracture toughness were studied. Used techniques were instrumented nanoindentation and KIC evaluation. As a result coatings with nearly 100% improvements in relative fracture toughness were produced for nanoreinforced alumina composite coating. Results are compared with the microstructure, hardness and abrasive wear resistance of the coatings.