Utilizing polymers for asphalt concrete (AC) mixture modification has many drawbacks that hinder its wide implementations for roadway construction. Recently, research on employing complementary materials, such as nanomaterials, to balance negative impacts of polymers while enhancing the AC mixture’s performance has received great attention. This study aimed to investigate the effect of incorporating nanoclay (NC) particles on the performance of a high-density polyethylene (HDPE)-modified AC mixture. A 60/70 asphalt binder was first modified with HDPE, and then NC particles were gradually added at a concentration of 1–4% by weight of the asphalt binder. The binders’ physical characteristics, storage stability, and chemical change were scrutinized. AC mixture performance, including pseudo-stiffness, moisture damage resistance, stripping susceptibility, and rutting tendency, was investigated. A statistical analysis on the experimental results was conducted using Kruskal–Wallis and Dunn tests. Test results showed that employing NC/HDPE significantly increased penetration index and thereby enhanced binder temperature sensitivity. Moreover, it prevented oxidation action and separation and, therefore, enhanced binder storage stability. Furthermore, incorporating NC amplified pseudo-stiffness and significantly improved resistance against moisture damage and stripping of HDPE-modified mixtures. Moreover, it improved both elastic (recoverable) and plastic (unrecoverable) deformations of mixtures. The most satisfactory results were attained when incorporating 3% of NC.