The application properties of spray coatings may be tuned by microstructure design, which is critically influenced by the initial powder feedstock. (Ti,Mo)(C,N)–45vol.% (Ni–20wt.% Co) VPS-coatings based on (a) conventional coarse agglomerated and sintered powders or (b) high-energy milled nanocrystalline powders were compared to elucidate different wear properties and mechanisms. Coatings based on nanocrystalline feedstock show finer and more homogeneous microstructures as well as significantly higher hardness and toughness. They appear mechanically like a homogeneous and more ductile material, thus showing continuous wear grooves. Under high stress, nanocrystalline coatings have superior wear resistance by a factor of 2 and are more reliable due to higher fracture toughness. Under low stress, the nanocrystalline coatings show a slightly higher wear, however, with more homogeneous material loss, lower friction coefficient, and smoother worn surface. For application, this may be more important than the actual loss of material, regarding surface quality and lifespan of the mating components.