Cold Mix Asphalt Emulsion (CMAE) has the potential to serve as an environmentally friendly, efficient, and accessible alternative for road construction, as it eliminates the need for heating during production and can be compacted at low temperatures. One of the key factors affecting CMAE performance is the aggregate gradation used in the mixture. This study aims to analyze the effects of aggregate gradation on the volumetric characteristics, mechanical properties, and durability of CMAE. Laboratory experiments were conducted using several aggregate gradation types. The results indicate that the middle-limit gradation (G. L2) produced the highest dry density, while the lowest air void content was found in gradation G. L1. The mechanical properties, including soaked stability and Indirect Tensile Strength (ITS), were positively correlated with dry density, as they are influenced by aggregate structure, the asphalt emulsion content, and its asphalt adhesion quality. CMAE durability measured through moisture susceptibility (TSR) and mass loss (Cantabro loss test) was affected by the gradation type, asphalt–aggregate bonding, and water content in the mixture. Overall, aggregate gradation plays a critical role in determining CMAE performance. Notably, optimal performance is achieved when the mixture has fully lost its moisture, allowing for maximum asphalt binding efficiency. These findings highlight the importance of selecting appropriate aggregate gradation in CMAE design to enhance performance outcomes.