Conventional and nanocrystalline MCrAlY coatings were applied by the high-velocity oxy-fuel (HVOF) deposition process. The ball-milling method was used to prepare the nanocrystalline MCrAlY powder feedstock. The microstructure examinations of the conventional and nanocrystalline powders and coatings were performed using X-ray diffraction (XRD), high-resolution field emission scanning electron microscope (FESEM) equipped with energy-dispersive X-ray spectroscopy (EDX), transmission electron microscope (TEM), and X-ray photoelectron spectroscopy (XPS). Williamson-Hall analyzing method was also used for estimation of the crystalline size and lattice strain of the as-milled powders and sprayed coatings. Owing to the investigation of the oxidation behavior, the freestanding coatings were subjected to isothermal and cyclic oxidation testing at 1000 and 1100 °C under static air. The results showed that the conventional as-sprayed MCrAlY coating had a parabolic behavior in the early stage and prolonged oxidation process. On the contrary, in the case of the nanocrystalline MCrAlY coating, the long-term oxidation behavior has deviated from parabolic to sub-parabolic rate law. Moreover, the results also exemplified that the nanocrystalline MCrAlY coating had a greater oxidation resistance following the creation of a continuous and slow-growing Al2O3 scale with a fine-grained structure. The nucleation and growth mechanisms of the oxides formed on the nanocrystalline coating have also been discussed in detail.