The interfacial bond characteristics and failure mechanism of near-surface mounted (NSM) fiber reinforced polymer (FRP) composites play an important role in the behavior of NSM strengthened concrete members. This bond characteristics under fatigue loading is less understood comparing to their static performance. In this study, a series of direct pull-out tests on NSM carbon FRP (CFRP)-concrete block specimens were performed under fatigue loading conditions with a sinusoidal waveform at a frequency of 2 Hz. Prior to any fatigue loading, monotonic test was also conducted to respective reference specimens to establish the corresponding static capacity (i.e., ultimate pull-out force). Degradation of the local bond strength is presented in this paper for both CFRP rods and strips under the fatigue load ranging from 10% to 60% of the corresponding static load-carrying capacity. The effect of cross-sectional shape, surface treatment and adhesive type on the fatigue bond characteristics of the NSM CFRP in concrete is also discussed in this paper.