Stepwise phase change material (PCM) aggregate concrete has advantages in controlling temperature and resisting frost heave, but its freeze–thaw resistance performance is still unclear. This paper explored the impact of replacing ordinary coarse aggregate with stepwise aggregate on the freeze–thaw resistance characteristics of concrete. Firstly, the compressive strength, splitting tensile strength, and their relationship were evaluated. Then, the freeze–thaw resistance properties of PCM aggregate concrete were investigated, including macroscopic changes, mass loss, relative dynamic elasticity modulus loss, and compressive strength loss. Subsequently, the pore changes before and after freeze–thaw cycles were tested through non-destructive testing and nuclear magnetic resonance (NMR) testing, and the evolution of pores under freeze–thaw cycles was explored. The results show that adding 100% PCM aggregate reduces the strength of concrete by 32%. However, due to the high porosity in the 100% PCM aggregate concrete, it would have an adverse impact on corrosion resistance. The corrosion resistance of concrete increases firstly and then decreases with the addition of PCM aggregate, which can be attributed to PCM aggregate having a limiting effect on pore development. Overall, a substitution rate of 60% is acceptable for compressive strength and corrosion resistance.