Poor formability of rolled magnesium (Mg) alloys extremely restricts applications in form of sheets originating from formation of strong basal texture. Recently, we found that increasing rolling temperature from 723 to 798 K for a AZ31 Mg alloy can significantly improve stretch formability due to remarkable texture weakening after annealing. In this study, static recrystallization behaviors of AZ31 alloy sheets rolled at 723 and 798 K were investigated by electron backscattered diffraction analyses at different annealing stages in order to understand the origin of high temperature rolling on texture weakening. For both sheets, similar deformation microstructures with approximately the same types and fractions of twins exist in the as-rolled condition and recrystallized grains are mainly formed at pre-existing grain boundaries due to discontinuous recrystallization during subsequent annealing. However, only the basal texture of the latter remarkably weakens due to the formation of new recrystallized grains with well-dispersed orientations. Non-basal slips enhanced during high temperature rolling at 798 K are most likely responsible for the texture randomization as a result of rotations of recrystallization nuclei.