Debonding failure mode usually occurs in the concrete structure flexural strengthened with fiber reinforced polymer (FRP) under cyclic loading. This paper presents an experimental investigation into the fatigue behavior of the FRP-concrete interface of reinforced concrete (RC) beams strengthened with prestressed FRP. 8 small-scale beams were tested under three-point bending cyclic loading. The propagation behavior of the fatigue interface cracks is addressed, and curves showing the growth law of interface cracks are presented. Results from these tests show that the propagation process of interface cracks had three stages, including rapid, stable and unstable growth. The stable propagation phase experienced the most part of the whole test, and the failure mode of all failed beams was debonding following the fatigue fracture of the tensile steel bars. In addition, the influence of FRP prestressing level on the fatigue lives of strengthened beams is discussed, and an empirical formula is developed to predict the fatigue lives of such members. The results show that the fatigue life increases with the prestressed level of FRP. This study provides an insight on the potential long-term performance of FRP-strengthened beams submitted to fatigue loading conditions.