Nanostructured 316L stainless steel coatings with and without Al were deposited on stainless steel substrates to evaluate the potential gain in oxidation resistance. Compared to the base alloy, nanostructured samples had thicker thermally grown oxides, independent of tested temperature. The oxides formed, however, were enriched in Cr, which was found to increase oxidation resistance. The addition of Al (2 and 6 wt-%) yielded an Al2O3/Cr2O3 oxide scale, which significantly increased the oxidation resistance compared to other samples. The nanostructured alloys had roughly half the activation energy for oxidation, and lower oxidation rate constants, than the conventional coatings.