Thermal energy storage recycled powder mortar (TESRM) was developed in this study by incorporating paraffin/recycled brick powder (paraffin/BP) composite phase change materials (PCM). Fourier transform infrared and thermogravimetric analysis results showed that paraffin/BP composite PCM had good chemical and thermal stability. The onset melting temperature and latent heat of the composite PCM were 46.49 °C and 30.1 J·g⁻¹. The fresh mortar properties and hardened properties were also investigated in this study. Paraffin/BP composite PCM with replacement ratio of 0%, 10%, 20%, and 30% by weight of cement were studied. The results showed that the static and dynamic yield stresses of TESRM were 699.4% and 172.9% higher than those of normal mortar, respectively. The addition of paraffin/BP composite PCM had a positive impact on the mechanical properties of mortar at later ages, and could also reduce the dry shrinkage of mortar. The dry shrinkage of TESRM had a maximum reduction about 26.15% at 120 d. The thermal properties of TESRM were better than those of normal mortar. The thermal conductivity of TESRM was 36.3% less than that of normal mortar and the heating test results showed that TESRM had good thermal energy storage performance.