This study investigated RCA as a sustainable, cost-effective NA substitute in road construction. Mixtures with 0–100% RCA were tested under freeze-thaw (F-T) cycles for resilience and deformation, compared to non-exposed controls. The F-T cycles, mix composition, and stiffness are interrelated. The resilient modulus of NA-RCA mixtures increased for up to 5 F-T cycles, then slightly dropped. The 50% NA + 50% RCA mixture showed improved stiffness, with average MR increasing from about 321 MPa to 420 MPa. The 100% NA sample’s average MR dropped from about 220 MPa to 196 MPa after 5 F-T cycles. As RCA content increased to 50%, plastic deformation decreased from about 0.085% and then slightly increased. The 50% NA and 50% RCA blend showed the least plastic deformation (0.065%) in all F-T cycles, demonstrating RCA’s effective use in road construction. This composition showed great stiffness and resilience even after multiple freeze-thaw cycles. These results support sustainable road construction without compromising performance. It is essential to note that the study’s scope was limited to laboratory conditions, which may not fully represent real-world conditions. Future research should field test RCA and NA mixtures in various environments to validate the findings and assess long-term performance.