The present paper describes the synthesis of nanocrystalline 316-stainless steel coatings by high velocity oxy-fuel (HVOF) thermal spraying. The feedstock powders were synthesized by mechanical milling to produce flake-shaped agglomerates with an average grain size of less than 100 nm. The powders were introduced into the HVOF spray to successfully produce nanocrystalline coatings. X-ray diffraction analysis and transmission electron microscopy were used to determine the average grain size of the milled powders. Scanning electron microscopy and transmission electron microscopy were used to study the morphology of the nanometric particles and the microstructure of the as-sprayed coatings. The properties of various coating materials were characterized by microhardness measurements performed on the polished surface of the cross section.