Microstructure evolution and fracture morphology during high cycle fatigue in AZ31 magnesium alloy were investigated by fatigue test at different loading frequencies (3 and 30 Hz) and stress amplitudes (90, 95, 100, 105, 110 MPa). Electron back-scattered diffraction (EBSD) analysis results show that the number of residual twins in the matrix increases with the increase in loading stress, and the residual twins mainly exist in the form of {102} tensile twins. Gradual grain refinement is observed with increasing stress amplitude, which is due to the grain refinement induced by the evolution of tensile twinning during fatigue deformation. The significant weakening of the texture strength with increasing stress amplitude is related to the recrystallization mechanism after fatigue deformation. Through the scanning electron microscope (SEM) analysis of the fatigue fracture, it is found that the fatigue crack initiation (FCI) occurs in twin layer, the area of the fatigue crack growth (FCG) in the specimen gradually decreases with the increase in stress, and obvious fatigue striations (FS) are observed in FCG. The final fracture (FF) is rough surface, and there are mainly tear ridges and dimples. The dimple is observed in the final fracture, and the size and number of dimples decrease with the increase in stress.