This paper presents a study on coupled deterioration mechanisms, including carbonation and frost attack, on concrete prepared with 0, 50 and 100% by weight coarse recycled concrete aggregates (CRCA) to replace coarse natural aggregate (CNA). Fly ash (FA) was also used as 0, 20 and 40% weight replacements of cement. Carbonation depth, relative dynamic modulus of elasticity (RDME) and residual compressive strength were measured during the tests. Nuclear magnetic resonance analysis was performed on the selected samples to identify pores and cracks formed through coupled deterioration. Results showed that freeze–thaw cycle and carbonation affected each other. On the one hand, carbonation can increase strength and reduce permeability to improve freeze–thaw resistance and form new pores, which accelerate freeze–thaw damage. On the other hand, the depth of carbonated concrete increased as the freeze–thaw deterioration increased; this finding could be due to cracking associated with increased internal deterioration caused by freeze–thaw cycle. In contrast to the findings of the single-factor test, concrete subjected to coupled deterioration by freeze-thaw and carbonation showed lower residual compressive strength and residual RDME but higher carbonation depth.