The present study is focused on investigating the deterioration mechanism of the anti-frost performance of concrete mixed with construction waste composite powder material (CWCPM), taking into account the effect of the water–cement (w/c) ratio, dosage of CWCPM, sodium chloride (NaCl) solution concentration and freeze–thaw (F–T) cycles, through macroscopic and microscopic tests. Two regression models were obtained for quantifying the deterioration of the anti-frost performance. In addition, the damage evolution process of the microstructure, interfacial transition zone and pore structure of concrete with CWCPM due to F–T cycling was analyzed. The significant influence of pore structure parameters on the macroscopic frost resistance of concrete was also analyzed by gray relational analysis. The results show that increases in w/c ratio and the number of F–T cycles and the existence of solutes can aggravate the damage of concrete, while the CWCPM positively influences both the anti-frost performance and microstructure of concrete. The sodium chloride solution significantly contributes to the damage of concrete subjected to F–T cycling. The macroscopic frost resistance of concrete is closely related to its internal microstructure. The essence of F–T damage is the physical change in the internal microstructure of concrete from compact to loose and the progressive deterioration of the pore structure.