Modification of asphalt binders has been one of the common techniques to overcome the climatic and traffic-related distresses that develop in bituminous materials. Over the past decade, many new methods of incorporating recycled tire rubber as a modifier have been developed and evaluated by states and county road departments. This study focuses on the use of the so-called devulcanized recycled tire rubber modifier and its effects on the performance grade, fatigue cracking resistance, and rutting resistance of asphalt binder. Devulcanized rubber was incorporated into hot liquid asphalt at various percentages using high and low shear blending, consecutively. First, the effect of modifications on continuous performance grades (PG) at low, intermediate, and high temperatures was investigated. Second, equistiffness temperatures of the binder-rubber mixes were established, and the fatigue cracking resistances of the rubber-binder blends were measured by using the linear amplitude sweep (LAS) test at different strain levels. Last, the multiple stress creep and recovery test (MSCR) was conducted on the modified asphalt samples to characterize the high-temperature performance. Although there was a significant improvement on high PG as the modifier amount increased, the improvement for intermediate and low PGs was minimal. The same trend observed for high PG of the modified asphalt binders was also obtained for fatigue cracking resistance and rutting resistance. The results showed that the use of devulcanized rubber modification could successfully extend the life of bituminous materials.