In order to effectively identify the early fatigue cracks of the steel bridge deck under vehicle loads, the numerical and experimental research on the nonlinear Lamb wave detection of steel plate fatigue cracks were carried out. Based on the non-linear theory of acoustic contact, three damage indexes were proposed, which are first wave energy, pseudo sound velocity and nonlinear parameter. Three types of defects including hole defect, macro crack and fatigue crack were considered in the specimens. Among them, the fatigue growth crack was generated by the fatigue loading test. In the three-dimensional numerical model, the “breathing effect” of closed crack is simulated by a zero-length nonlinear spring element to simulate the local nonlinear interaction process between Lamb waves and fatigue cracks. In the experiment, the nonlinear Lamb wave stepped scanning was performed, and the harmonic response was extracted through a band pass filter. The research results show that the first wave energy and pseudo sound velocity are sensitive to macro defects, while the harmonic waves energy and nonlinear parameter are sensitive to fatigue cracks. Combining the three damage indexes can simultaneously achieve the identification and location of macro defects and fatigue cracks.