A damage-based model was developed for the bond behavior between fiber-reinforced-polymer (FRP) bar and concrete under high-cycle fatigue loading. The high-cycle fatigue nonlinearity is simulated using two separate damage parameters for reproducing the bond stiffness degradation and residual slip growth. The developed damage model was combined with a ‘cycle jump’ technique to reduce the computational time based on selecting a set of loading cycles. The model was implemented in a 3D finite-element (FE) code, with the aim of simulating the relevant experimental pullout tests. The sensitivity of the fatigue model to the damage parameters and its good predictive performance were demonstrated.