The mechanical behavior of asphalt binder is highly sensitive to temperature. The manner in which mechanical characteristics change with temperature can also vary significantly from one asphalt to another. With such variations, grading the rutting resistance of the binder by measuring a mechanical parameter of the binder at a single temperature will not be accurate, nor will ranking by determining the temperature at which a mechanical property reduces to a certain value. For precise characterization of rutting resistance of asphalt binders, a high-temperature binder specification should take into account both the sensitivity of mechanical behavior to changes in temperature and the variations in such temperature sensitivity from one binder to another. This study conducts an experimental investigation and an analysis of existing data in the literature to examine the nature of the temperature dependence of the various material parameters used to characterize rutting resistance of binders. Particularly, the nature of the temperature dependence of the nonrecoverable creep compliance from multiple stress creep recovery (MSCR) tests is investigated. The Arrhenius relationship is found to fit the relationship between mechanical properties and temperature in the high-temperature range reasonably accurately. The activation energy corresponding to the Arrhenius equation, however, is found to vary significantly between the binders. Taking these issues into consideration, a new approach to grading the rutting resistance of asphalt binders is developed that uses the Arrhenius-like temperature dependence exhibited by asphalt binders. © 2018 American Society of Civil Engineers.