A study was conducted to ascertain the changes in viscoelastic parameters with the increase in fatigue damage of asphalt mixtures. In the present study, it was ascertained how the viscoelastic parameters changed with the increase in the fatigue damage of asphalt mixtures by conducting the repeat compressive-tensile test using cylindrical specimens compacted using the Superpave Gyratory Compactor. The viscoelastic parameters, including dissipated energy and phase angle, were affected by the strain amplitude, test temperature, and penetration value. The relationship assessment between the viscoelastic parameters and the number of cycles to failure reveals that the fatigue characteristics are influenced by the dissipated energy accumulation and the phase angle changes in the fatigue process. The number of cycles to failure of the asphalt mixture was correlated with the total dissipated energy accumulated until fatigue failure and the change in phase angle in the fatigue process. The fatigue damage of asphalt mixture increased significantly when the asphalt mixture exhibited viscoelasticity and the unit dissipated energy reached its maximum value. The repeated compressive-tensile test can assess the viscoelastic parameters of the cylindrical core samples obtained from the field in both their fatigue damage state and the asphaltic concrete layer’s remaining life.