An effective way to improve the rutting resistance of asphalt pavement is to increase the modulus of the middle surface layer of the asphalt mixture. However, the fatigue performance of high-modulus asphalt mixtures hinders this development. In this study, we enhanced the fatigue property of high-modulus asphalt mixtures by adding basalt fiber. Marshall tests were performed to evaluate the effect of the basalt fiber and a high-modulus modifier on various Marshall test results. The results were analyzed and compared with the performance of SBS-modified (Styrene-Butylene-Styrene) asphalt mixes. Adding basalt fiber increased the asphalt-aggregate ratio, decreased the density, and reduced air voids in the mixture. The stability also slightly increased, and the flow slightly decreased. Moreover, 0.2% basalt fiber increased the fatigue resistance of high-modulus asphalt mixture 1.9 times, and this improvement increases with the increasing basalt content. The elastic modulus of basalt fiber is considerably higher than that of asphalt; therefore, the proportion of stiffer components in the asphalt mastic was higher after mixing. Furthermore, basalt fiber absorbs oil (asphalt); accordingly, the increased asphalt content slightly enhanced the fatigue resistance of the mixture.