An interesting change of scale sequence occurred during oxidation of nanocrystalline surface layer by means of a surface mechanical attrition treatment. The three-layer oxide structure from the surface towards the matrix is Fe3O4, spinel FeCr2O4 and corundum (Fe,Cr)2O3, which is different from the typical two-layer scale consisted of an Fe3O4 outer layer and an FeCr2O4 inner layer in conventional P91 steel. The diffusivity of Cr, Fe and O is enhanced concurrently in the nanocrystalline surface layer, which causes the fast oxidation in the initial oxidation stage. The formation of (Fe,Cr)2O3 inner layer would inhabit fast diffusion of alloy elements in the nanocrystalline surface layer of P91 steel in the later oxidation stage, and it causes a decrease in the parabolic oxidation rate compared with conventional specimens. This study provides a novel approach to improve the oxidation resistance of heat resistant steel without changing its Cr content.