Initiation of recrystallized grains was observed under high-temperature low-cycle fatigue conditions in austenitic 18Cr-8Ni stainless steel. The fatigue tests were carried out using unbalanced fast-tension and slow-compression triangular strain wave-shape at 973 K in air. Recrystallized grains were initiated and grew along grain boundaries with the number of fatigue cycles. Accumulated grain-boundary sliding is considered to be the driving force for the recrystallization. Effects of the recrystallized grain structure on high-temperature fatigue failure were then examined under the conditions in which intergranular fatigue failure occurred. The recrystallized grain structure had no detrimental effects on the intergranular failure. The fatigue life was somewhat increased by the initiation of recrystallized grain structure.