The objective of this study was to investigate the rutting performance of gap-graded aggregate gradations in conjunction with the effect of asphalt binder. Two gap-graded aggregate gradations recommended by Arizona Department of Transportation (ADOT: gradation A), Texas DOT (gradation B), and one newly proposed gradation (gradation C) were considered in this study. Wheel-tracking test was performed at 60 °C on ten asphalt mixtures, and rut depth was statistically analyzed using 23 factorial designs at 95% confidence interval. Main effect analysis showed that gradation C offered the highest rutting resistance followed by gradation B and A. Though the gradation A demonstrated a reduction in rutting resistance with increasing binder content, gradations B and C were less sensitive to variation in the binder content. Rutting characteristics estimated at different stages revealed that permanent deformation incurred in gradation A developed rapidly until 75% and then retarded to a stable rate. In the case of gradations B and C, there was a marginal difference in the permanent deformation at various stages. Further, gap-graded asphalt mixtures prepared with gradations B and C at both (OBC − 1) and OBC % showed better performance than conventional dense-graded (DG) asphalt mix. Overall, it was concluded that gap-graded mixture can be expected to outperform the DG mix when designed with appropriate mix parameters. © 2020, Springer Nature Singapore Pte Ltd.