Abstract: Material early mechanical degradation is associated with the micro-structural changes such as dislocation and slip band. When a single sinusoidal ultrasonic wave is launched to a nonlinear medium, the higher harmonics will be generated. This research develops a robust experimental procedure. There is linear relationship between amplitudes of the second-harmonic waves and the squared fundamental waves as a function of increasing input voltage amplitude, the linear correlation coefficient r= 0.9996. The experimental system is reliable. Using this system, ultrasonic nonlinearity parameters β of three groups of Magnesium samples with different loading stress are measured. The experimental results show that there is a significant increase in β linked to fatigue degree in the early stages of fatigue life and reaches the maximum about 55% of fatigue life, β can characterize the early fatigue damage of Magnesium. However, in the context of middle and low-cycle fatigue, changes of loading stress and the fatigue model with tension-tension fatigue and tension-compression fatigue had no significant effect to the experimental results.