This paper presents an analytical solution for the evolution and distribution of shear stresses along the entire bond length of FRP-concrete interfaces due to mode-II fatigue loading. The creep-fatigue interaction and fatigue crack growth after debonding initiation are incorporated into a nonlinear interfacial constitutive law. While the creep-fatigue interaction is represented by the degradation of the interfacial stiffness, the debond growth is governed by a form of the Paris equation and the fracture energy ratio, Gmax/Gc. Furthermore, a new form of energy ratio is adopted to be debond-dependent. Through a series of experimental double-lap shear specimens, the results showed that the debond growth rate (da/dN) along the FRP-concrete interfaces diminishes with fatigue cycles and that 30% of the static bond capacity of the FRP-concrete interface can be considered as the endurance limit of fatigue loading for FRP-strengthened beams. The agreement between the theoretical predictions and experimental results is valid, with a good degree of accuracy.