The fatigue behavior of recycled aggregate concrete (RAC) with 100% recycled coarse aggregate (RCA) replacement percentage under uniaxial compression was experimentally investigated in this study. Key quantities, including the residual strain variation, fatigue strain variation and the fatigue modulus of RAC, were calculated and analyzed to correlate the strain response and fatigue damage behavior of RAC. It is found that there exist no obvious differences of compressive fatigue behavior between RAC and natural aggregate concrete (NAC). Based on the experimental results and continuum damage mechanics, a fatigue model relating the fatigue strain variation and the fatigue modulus degradation to the fatigue damage evolution is proposed. Furthermore, RAC with 100% RCA replacement percentage was also tested under cyclic bend loading. It is found that the fatigue life of RAC is lower than that of NAC for the same stress level under cyclic bend loading.