In order to monitor the early fatigue damage of AZ31 magnesium alloy by nonlinear ultrasonic, a nonlinear FEM model is established by a special element which accounts for a nonlinear stress-strain relation. The influence of the micro-defect with different length, quantity and width to ultrasonic nonlinearity parameters is calculated. The simulation results show that micro-defects in material fatigue is the cause of the second harmonic generation, finite element method can effectively simulate ultrasonic nonlinear effects in magnesium alloy material. Meanwhile, ultrasonic nonlinearity parameters of two magnesium samples are online measured. There is a significant increase inlinked to fatigue cycles in early stages of fatigue life, but at the late stage of fatigue, an experimental phenomenon of the decrease in fatigue cycles is obtained. The experimental results show that ultrasonic nonlinearity parameters can characterize the early fatigue damage of magnesium. The results of simulation verify experimental results.