This article presents freeze-thaw (F/T) resistance of concrete containing recycled concrete aggregate (RCA). RCA percentages of 15%, 30%, 45%, and 60% were replaced by natural aggregate. Air entraining admixture (AEA) with three different ratios (0.06%, 0.13%, and 0.20%) were used and three different maximum aggregate particle sizes (dmax = 16 mm, 22.4 mm and 31.5 mm) were selected. F/T resistances of the concretes were determined through the measurement of scaling on the surfaces of the samples placed in 3% NaCl solution in pursuance of TS CEN/TS 12390-9. It was observed that the compressive strength of the concretes decreased by 20% on average compared to the control samples with the increase in the amount of RCA. However, it was determined from the experiments that the use of RCA increases the F/T resistances of the concretes as it provides extra voids in the concrete and decreases capillary permeability. Within the limits of this study, dmax = 22.4 mm, RCA = 45% and AEA = 0.13% are recommended as the optimum values for F/T resistance of the concrete. It is also recommended to use RCA in pavement applications including roadways, highways, parking facilities, and other non-structural concrete elements subjected to severe winter conditions.