The purpose of this study is to improve the examining and understanding of the bonding behavior of Fiber Reinforced Polymer (FRP) sheets bonded to concrete blocks and steel plates under fatigue loading. First, a series of experimental investigations is summarized in the paper. The fatigue behavior of bonding surface between FRP sheets and concrete is finally characterized by the conducted P-S-N diagram representing the relationship among the probability of FRP debonding (P), the bond stress amplitudes (S), and the number of cycles (N) at debonding on a semi-logarithmic scale. The different debonding modes for various fracturing surface are also investigated and evaluated.