Experimental studies have evidenced that the use of Fibre Reinforced Polymer (FRP) composite materials to reinforce or strengthen the RC structures exposed to repeated cyclic loading can improve their fatigue life. To exploit the good fatigue performance of these composite materials, the bond between the FRP reinforcement and the concrete must remain effective. The current study aims to simulate the nonlinearity in the bond of FRP rebar and concrete under high-cycle fatigue, firstly, by developing a damage-based model for reproducing the bond stiffness degradation and residual slip growth due to fatigue load effects, and then, developing a 3D finite element (FE) model in a commercial software. The FE model considers the nonlinear behaviour of the materials coupled with the developed damage-based model to simulate the bond deterioration due to high number of cycles. Moreover, to reduce the computational cost for modelling each cyclic loading, a cycle jump approach is implemented in the FE model. The developed numerical model is validated by comparing with the relevant results of an experimental program involving eccentric pull-out fatigue tests.