Utilizing phase change materials and carrier materials to prepare phase change particles, replacing concrete aggregates for the production of phase change concrete, represents a novel technique for enhancing the durability of concrete in cold regions. In order to investigate the correlation between the compressive strength of PCC and its pore characteristics, a novel type of phase change particles with cement-encapsulated, named EPC14, was prepared by using n-tetradecane (C14) and expanded perlite (EP) as raw materials. Subsequently, phase change concrete (PCC-EPC14) was prepared by replacing fine aggregates at an equal volume. The PCC-EPC14s underwent 50, 100, 150, and 200 freeze-thaw cycles. Then, uniaxial compression tests and nuclear magnetic resonance tests were uesd to test the compressive strength and pore characteristics of the PCC-EPC14s. Finally, the fractal dimension of the PCC-EPC14s was calculated using fractal theory, and the relationship between compressive strength and fractal dimension was analyzed. The results show that the optimal volume replacement ratio of phase change particles to fine aggregates is 20%. At this ratio, the PCC-EPC14 (20%) exhibites the maximum NMR (nuclear magnetic resonance) fractal dimension, minimum porosity, and maximum compressive strength after 200 freeze-thaw cycles. Additionally, a proportional relationship is observed between compressive strength and NMR fractal dimension, while an inverse relationship is found with relaxation time signal area.