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.