In this study, homogeneous metal and gradient porosity skeletons were constructed using the three-periodic minimal surface method (TPMS). Based on the pore scale, the finite element method was used to simulate the solidification process for a pure paraffin cavity and investigate the influence of the skeleton structure in the solidification of a composite phase-change material. Comprehensive analyses of the solid-liquid phase change interface, overall liquid phase rate, Nu number of the cold source wall, and cold-storage performance were conducted, and the following conclusion was obtained. When the TPMS skeleton was added to the phase change cavity, it affected the solid-liquid deformation process. The solidification time of the phase change chamber with a porosity of 0.78 is shortened by 94.1% and the cooling rate is increased by 12.98 times compared to the pure paraffin phase change chamber. When the average porosity is 0.84, the porosity gradient increases along the positive x-direction, accelerating the solidification of the cavity, improving the heat transfer efficiency of the chamber. Compared with the pure paraffin phase change chamber, the solidification time is shortened by 93.5%, and the cold storage rate is increased by 12.6 times. Compared with the same porosity and uniform TPMS skeleton phase change cavity, the solidification time is shortened by 12.23% and the cooling rate is increased by 15.3%.