Load associated fatigue cracking is one of the major distress types occurring in flexible pavement systems. Flexural bending beam fatigue laboratory test has been used for several decades and is considered to be an integral part of the new superpave advanced characterization procedure. One of the most significant solutions to prolong the fatigue life for an asphaltic mixture is to utilize flexible materials as rubber. A laboratory testing program was performed on a conventional and Asphalt Rubber- (AR-) gap-graded mixtures to investigate the impact of added rubber on the mechanical, mechanistic, and economical attributes of asphaltic mixtures. Strain controlled fatigue tests were conducted according to American Association of State Highway and Transportation Officials (AASHTO) procedures. The results from the beam fatigue tests indicated that the AR-gap-graded mixtures would have much longer fatigue life compared with the reference (conventional) mixtures. In addition, a mechanistic analysis using 3D-Move software coupled with a cost analysis study based on the fatigue performance on the two mixtures was performed. Overall, analysis showed that AR modified asphalt mixtures exhibited significantly lower cost of pavement per 1000 cycles of fatigue life per mile compared to conventional HMA mixture.