The transition from severe to mild wear is an interesting phenomenon that is usually attributed to the nanocrystalline “glaze” layer and subsurface ultrafine grain layer. However, the formation of “glaze” layers and subsurface layers and their effects on the wear mechanism are still unclear. The high-temperature tribological behaviors of the DD5 single-crystal superalloy and the electro spark-deposited NiAlTa coating were investigated at 25–1,000 °C by a high-temperature tribometer. The microstructures, chemical compositions, and grain orientations of the “glaze” layers and subsurface layers were studied. NiAlTa coatings show excellent wear resistance compared with DD5 superalloys, which is attributed to the excellent high-temperature softening resistance, high microhardness of the “glaze” layer, and good strain-hardening capacity of the subsurface ultrafine grain layer. Quantitative analysis reveals that whether the oxides on the wear surface play an anti-wear lubrication role depends on the content and properties of the oxides. The 100-fold difference in the wear rate indicates that the high-temperature wear resistance of the material is related to the chemical composition and microstructure of the “glaze” layers and subsurface layers. A mechanistic model is proposed to describe the evolution of nanocrystalline “glaze” layers and subsurface ultrafine grain layers.