Rutting (permanent deformation) is the most important distress that asphalt concrete pavements are prone to at high temperatures. However, available classical viscoplastic (VP) theories are incapable of properly predicting permanent deformation of asphalt concrete materials at high temperatures subjected to cyclic loading conditions. A physically based VP hardening relaxation model is proposed to overcome this issue. This model considers the changes in the microstructure that occur during the rest period and cause the induced hardening stress to relax and recover. This mechanism affects the VP properties of asphalt concrete before and after the rest period is applied. A memory surface is introduced as the general criterion for the evolution of the hardening relaxation mechanism. The memory surface possesses a state variable memorizing the history of the VP deformation during the loading history. The proposed VP hardening relaxation model is coupled with Schapery's viscoelastic model and the classical Perzyna's VP model and is validated against extensive experimental data, including repeated creep and recovery tests at different stress levels, loading times, and rest periods. It is shown that the proposed model reasonably predicts the cyclic VP response of asphalt concrete materials at high temperatures.