Load-associated fatigue cracking is one of the major distress types occurring in flexible pavement systems. Bending flexural beam fatigue testing has been used for several decades and is considered to be an integral part of the new Superpave advanced characterization procedure. However, there is a great need to assess and develop a fatigue criterion based on initial and failure stiffness of the mixture under consideration. A laboratory testing program was performed on a Reference, Asphalt Rubber (AR), and Polymer modified-gap graded mixtures. Strain-controlled fatigue tests were conducted according to American Association of State Highway and Transportation Officials (AASHTO) procedures on all of the three mixtures at one temperature. Using a COANOVA statistical analysis approach, the Arizona State University (ASU) method, which is independent on the mode of loading, temperature, frequency, or mixture formulation, was concluded to be the most accurate method to analyze beam fatigue results. This method has the potential for unifying current fatigue analyses using a rational energy-based approach and it has a well-defined fatigue failure point when compared with other proposed methods. It was also concluded that the AR mixture showed higher fatigue life than the Polymer and the Reference mixtures.