This study investigates the potential of two bitumen modifiers, high-density polyethylene (HDPE) and nano clay (NC), to enhance the rutting resistance of asphalt mixture. Four HDPE asphalt binders were prepared by mixing the HDPE at percentages of 2%, 4%, 6%, and 8% with the virgin binder, while four NC asphalt binders were produced by mixing the NC at percentages of 1%, 2%, 3%, and 4%. The consistency and flow of virgin binder, HDPE binders, and NC binders were evaluated by penetration, softening point, and viscosity tests. The results show a gradual increment in the binder stiffness by increasing the percentage of both modifiers. The static creep test was conducted at a temperature of 40 ◦C to evaluate the rutting resistance. The results confirm that both modifiers can greatly improve the rutting resistance of the asphalt mixture, where 8% HDPE and 3% NC modifications reduce the strains provoked in the asphalt mixture under loading by about 50%. According to the correlation analysis, the mixture rutting performance is highly attributed to the binder stiffness, where the lower the penetration value of the asphalt binder, the lower the strains in the asphalt mixture and the higher the stiffness modulus of the asphalt mixture.