Fatigue damage affects both durability and safety, and it has been the most important distress in asphalt concrete. Fatigue damage occurs as a result of repeated traffic loading. An asphalt mixture is a typical viscoelastic material, and its fatigue damage is related to its viscoelastic properties. Under repeated traffic loading, the combined effects of creep damage and fatigue damage will shorten its fatigue life. Currently, the evaluation of the fatigue damage of asphalt mixtures rarely considers the combined effects of creep damage and fatigue damage. To solve this problem, a viscoelastic fatigue damage prediction model of an asphalt mixture considering the combined effects of creep damage and fatigue damage is put forward by introducing parameter β and a displacement factor based on theoretical derivations and testing. The results show that the model can embody the viscoelastic fatigue damage essence of asphalt mixtures, and it can also consider the effects of aging degree, temperature, load frequency and stress on fatigue damage of asphalt mixtures. The maximum relative error of the testing and prediction results of fatigue life is 0.15, and it is a reasonable prediction model.