Since fiber-reinforced polymer (FRP) composites are inherently anisotropic and display a wide variety of failure mechanisms which interact with each other, predicting their fatigue behavior is a challenging task. Prediction of fatigue in FRP composites demands progressive damage analysis tools that account for the constituent physics of the problem. Such a methodology based on the kinetic theory of fracture (KTF) was used in this work to drive the progressive damage behavior of the matrix constituent both in intra and inter-laminar regions. The maximum stress criterion was utilized to determine fiber failure. Due to the wide variability of strength observed in composites, using a deterministic value for fiber strength is a poor choice. In this work, fiber tensile strength was assigned randomly to different elements of the composite open-hole tension (OHT) coupon to capture the stochastic nature of fiber failure under tension-tension fatigue loading. Matrix and fiber damage mechanisms were implemented together to capture the progressive damage behavior and the ultimate failure of OHT coupon. Simulation results were calibrated and validated with published experimental data, which show the robustness of the methodology in capturing the damage type and location, degradation of mechanical performance with accumulated damage, and variability of ultimate failure of the OHT coupons.