• Third-harmonic phase velocity matching nonlinear Lamb waves are used for the early fatigue damage detection of aluminum alloys. • The third harmonic first increases and then decreases with the accumulation of fatigue life. When the fatigue life reaches about 80%, the amplitude of the third harmonic declines sharply. • The third-order nonlinear parameters increase continuously with the accumulation of fatigue life. When the fatigue life reaches about 80%-90%, the third-order nonlinear parameters increase gradually and shows a downward trend. • The third harmonic and third-order nonlinear parameters are used as indicators of fatigue accumulation to realize detection of early fatigue damage. In this paper, third-harmonic phase velocity matching nonlinear Lamb waves are used for the early fatigue damage detection of aluminum alloys. An analysis is conducted regarding the relationship of third harmonic and third-order nonlinear parameters with fatigue accumulation. According to the analytical results, the amplitude of the third harmonic increases when the fatigue life falls below about 80%. However, when the fatigue life exceeds 80%, the third harmonic starts to decrease, and the third-order nonlinear parameters increase progressively before showing a downward trend. It can be found out that micro-cracks emerge with the accumulation of fatigue, thus reducing the amplitude of the third harmonic and causing the third-order nonlinear parameters to increase gradually and then decline. Furthermore, it is proposed to take the third harmonic amplitude and the third order nonlinear parameters as the indicators of early fatigue damage.