For practical engineering structures, fatigue is one of the main factors affecting their safety and durability. Under long-term service conditions, the minor damage will be affected by fatigue loading and expand to macroscopic cracks, affecting the structure’s service performance. Based on the sensitivity of Lamb waves to minor and initial damage, a damage monitoring method for fatigue crack propagation is proposed. By carrying out fatigue crack propagation tests under constant amplitude loading, the Paris equation of 316L steel and damage signals at different crack growth stages were obtained. Combined with damage monitoring tests and finite element analysis, the relationship between the phase damage index (PDI), amplitude damage index (ADI), signal correlation coefficient, and fatigue crack propagation length was studied. Compared with PDI and ADI, the signal correlation coefficient is more sensitive to crack initiation, which can be selected as the damage monitoring index in the initial stage of crack growth. With the increase of fatigue crack propagation length, the peak time of the direct wave signal gradually moves backward, which shows an obvious phase change. In the whole fatigue crack growth stage, PDI and crack length show a monotonically changing trend. By using the stress intensity factor as the conversion parameter, a prediction model of the fatigue crack propagation rate based on PDI was established. Compared to the fatigue crack propagation rate measured by experiments, the relative error of the predicted results is 10%, which verifies the accuracy of the proposed damage monitoring method.