The feasibility of fatigue damage evaluation has been investigated using nonlinear Lamb waves with group-velocity mismatching. To choose an efficient mode pair, a parameter is proposed to quantify the efficiency of cumulative second-harmonic generation (SHG) of Lamb waves based on the normal modal analysis. Experiments and simulations are performed to verify the proposed parameter, which demonstrates that whether the matching condition of group velocity is satisfied or not, the efficiency of cumulative SHG increases with the order of Lamb mode for the five low-order Lamb waves investigated. Then, S3-s6 mode pair with group-velocity mismatching is chosen to characterize the fatigue damage of an aluminium alloy for the high efficiency of cumulative SHG. Results show that S3-s6 mode pair is sensitive to fatigue damage evolution and the integrated amplitude of second harmonics increases by nearly 300% with fatigue cycles. Nonlinear Lamb waves with group-velocity mismatching are validated to be a candidate to efficiently evaluate the fatigue damage.