The objective of this research was to develop and evaluate asphalt-rubber gap-graded (AR-Gap) mixtures produced with varying gap aggregate gradations and designate a suitable aggregate gap gradation for local conditions, which could further be implemented at global level after necessary laboratory and field evaluations. A total of fifteen gap gradations were investigated, including seven specified by various highway agencies and eight trial gradations. The gradation studies recommended clustering seven gradations into two groups of similar characteristics. Furthermore, investigations on trial gradations presented the significance of each portion of the aggregate gradation in developing a superior performing gap gradation. Based on the refined gradation studies, three gap gradations were chosen: two from agency-specified, and one from the trial gradation for basic performance evaluation. Rutting, fatigue cracking, and moisture susceptibility investigations were accomplished on ten asphalt mixtures encompassing nine AR-Gap mixtures and one conventional dense graded mix. The results depicted superior performance of the proposed gradation indigenously developed in this study in respect of all distresses. The balance of coarse and fine aggregates in the proposed gradation facilitated higher strength at higher temperatures to resist rutting. Furthermore, the customized AR binder aided in providing additional resilience to the mixture, thereby improving the fatigue cracking resistance of the proposed AR-Gap mixture. Overall, it is envisaged that this study will help understand the effect of aggregate gradation characteristics on the performance of the AR-Gap mixture and aid in the development of AR-Gap mixtures as suitable long-lasting pavements. Copyright © 2018 by ASTM International