Rutting deformation is one of the most prominent diseases in asphalt pavement’s early damage. In this paper, the factors that affect the anti-rutting performance of asphalt pavement were studied. Firstly, the optimum asphalt dosage in the mixtures, and the change law of asphalt pavement’s anti-rutting performance were analyzed by model testing that considered changes in the mixture aggregates’ fractal dimension, asphalt dosage, temperature, wheel load, and air-void. Secondly, the grey entropy correlation coefficient between the influencing factors and mixtures’ dynamic stability was analyzed according to the Grey entropy theory. The results showed that the asphalt mixtures’ anti-rutting performance decreased as temperature and wheel load increased. Further, their anti-rutting performance increased firstly and then decreased with increased asphalt dosage, air-void, and fine aggregate. The optimum asphalt content for the rut test (OAC′) differed from that of the Marshall test (OAC), and OAC′ intermediated between type OAC-0.1% and OAC-0.3%. The fractal dimension showed the opposite trend to the aggregate thickness in the mixture, in which the aggregate was finer, while the fractal dimension was larger. Among all of these factors, the mixtures’ structural type affected its rutting resistance greatly, the influence of temperature and asphalt dosage in the mixture was similar and greater, the influence of the asphalt mixture’s air-void was second, and the wheel load had little effect. It is recommended that asphalt mixtures’ air-void ranges from 3.5 to 5.0%.