Fatigue damage accumulation will not only cause the degradation of material performance but also lead to the growth of effective stress and critical stiffness. However, the existing fatigue reliability models usually ignore the effective stress growth and its influence on the critical stiffness of a composite material. This study considers the combined effects of performance degradation and effective stress growth, and a pair of fatigue reliability models for a composite material are presented. Firstly, the fatigue damage in a composite material is quantified by its performance degradation, and the fitting accuracy of several typical fatigue damage models is compared. Subsequently, the uncertainties of initial strength and initial stiffness are considered, and a pair of probabilistic models of residual strength and residual stiffness are proposed. The performance degradation data of Gr/PEEK [0/45/90/−45]2S laminates are utilized to verify the proposed probabilistic models. Finally, the effective stress growth mechanism and its influence on the failure threshold are elaborated, and a pair of fatigue reliability models for composite materials are developed. Moreover, the differences between the strength-based and stiffness-based reliability analysis results of composite materials are compared and discussed. [ABSTRACT FROM AUTHOR]