We present theoretical investigations that clarify elemental nitridation processes of corundum Al2O3(0001) and (1102) surfaces. The calculations within the density functional theory framework reveal that the structures with substitutional N atoms beneath the surface are stabilized under nitridation conditions. We also find that the desorption of O atoms at the topmost layer induces outward diffusion of O atoms as well as inward diffusion of N atoms, leading to the transformation into AlN films. The kinetic Monte Carlo simulations in conjunction with density functional theory results indeed observe a dependence of these chemical and structural changes on temperature and pressure.