The objective of this study was to evaluate the rutting performance of asphalt-rubber gap-graded (AR-Gap) mixtures using wheel tracking tests and further explain the permanent deformation characteristics of those special materials through statistical and reliability approaches. A total of 28 asphalt mixtures covering over 200,000 data points were utilised, including: 27 AR-Gap mixtures and one conventional dense-graded (DG) mixture. Statistical analysis confirmed the significance of binder type, aggregate gradation, and binder content on the superior rutting resistance of AR-Gap mixtures than the DG mix. Selection of the best combination of all the three variables resulted in a significantly rut-resistant AR-Gap mixture. Reliability analysis on mixtures’ rutting performance was accomplished using Weibull distribution function. Weibull model parameters and derived factors aided in a better interpretation of the rutting performance of AR-Gap mixtures. Overall, it is envisaged that this research study would further the state-of-the-art in designing rut-resistant asphalt-rubber gap-graded mixtures. © 2019 Informa UK Limited, trading as Taylor & Francis Group.