A nonlinear Lamb-wave-based method for fatigue crack detection in steel plates with and without carbon fibre reinforcement polymer (CFRP) reinforcement is presented in this study. Both numerical simulation and experimental evaluation were performed for Lamb wave propagation and its interaction with a fatigue crack on these two steel plate types. With the generation of the second harmonic, the damage-induced wave nonlinearities were identified by surface-bonded piezoelectric sensors. Numerical simulation revealed that the damage-induced wave component at the second harmonic was slightly affected by the existence of CFRP laminate, although the total wave energy was decreased because of wave leakage into the CFRP laminate. Due to unavoidable nonlinearity from the experimental environments, it was impractical to directly extract the time-of-flight of the second harmonic for locating the crack. To this end, the correlation coefficient of benchmark and signal with damage at double frequency in the time domain was calculated, based on which an imaging method was introduced to locate the fatigue crack in steel plates with and without CFRP laminates.