The mechanical behavior of asphalt binders is nonlinear. The binders exhibit shear thinning/thickening behavior in steady shear tests and non-proportational behavior in other standard viscoelastic tests such as creep-recovery or stress relaxation tests. Moreover, they develop normal stress differences even in simple shear flows - a characteristic feature of nonlinear viscoelastic behavior. Many researchers have asserted the importance of considering the nonlinearity of the mechanical behavior of asphalt binders for accurately estimating their performance under field conditions, and for comparing and ranking them accordingly. In order to do so, it is necessary to have a robust and reliable nonlinear viscoelastic model. However, most of the models available in the literature do not capture the various features of the nonlinear response of asphalt binders accurately. Those that could are too complicated and still possess other shortcomings. Considering these issues, a new nonlinear viscoelastic model is developed here using a new Gibbs-potential based thermodynamic framework. The model is then corraborated with data from experiments in which the shear-thinning behavior and the nonproportional creep-recovery behavior were observed together. Finally, the model is used to evaluate the various criteria available for predicting rutting susceptibility of asphalt binders. Results of the analysis of the rutting prediction criteria show that each criterion characterizes the resistance to permanent strain shown by asphalt binders over a different range of applied stress - the zero-shear viscosity at very low stress levels, the Superpave criterion at very high stress levels and the MSCR test in the intermediate range of stresses.