Energy crisis and global warming demand development of high-performance structural materials to improve energy efficiency. For efficient energy conversion, the operating temperature and pressure of a heat engine used in boiler/steam turbine power plants should be as high as possible and materials used for the engine components must be able to withstand the high operating temperature. As such, next-generation structural materials simultaneously possessing higher creep strength and larger oxidation-resistance at elevated temperatures than those currently used are required. The conventional austenitic stainless steels, which rely on the formation of a tenacious Cr₂O₃ scale, would lose its protection capability at temperatures above 923 K, in particular in the presence of sulfur and water vapor. The alumina-forming austenitic (AFA) stainless steels are a relatively new class of dispersion-strengthened austenitic steels which showed superior oxidation-resistance to conventional stainless steels due to formation of the Al₂O₃-based protective scale at high temperatures. Recently, research focuses in this field have been mainly placed on high temperature oxidation-resistance, while little attention was paid to the mechanical property of these steels, particularly at elevated temperatures. In order to fully understand the deformation mechanisms at high temperatures, the recrystallization behavior in a typical AFA stainless steel under different conditions, including different annealing temperatures and durations, were investigated. The high-temperature mechanical properties of the AFA stainless steel samples heat-treated under different conditions were also studied. The sample was fully recrystallized upon heat treatment at 1473 K for at least 2 h and showed tensile strength about 130 MPa when tested at 1023 K with a strain rate 6.4×10^-7 s^-1. The specimen was partially recrystallized upon heat treatment at 1373 K for 0.5 h and exhibited a higher tensile strength of 150 MPa with decreased plasticity when tested under the same condition. Further investigation shows that the grain growth was influenced by the precipitation of NbC. The grain growth exponent, n, was determined to be 3 and the apparent activation energy for grain growth is 234.7 kJ/mol, which is consistent with that of the Nb diffusion along the grain boundary in the austenite.