Abstract: The challenge of high temperatures in deep mining remains harmful to the health of workers and their production efficiency. The addition of phase change materials (PCMs) to filling slurry and the use of the cold storage function of these materials to reduce downhole temperatures is an effective approach to alleviate the aforementioned problem. Paraffin–CaCl₂·6H₂O composite PCM was prepared in the laboratory. The composition, phase change latent heat, thermal conductivity, and cemented tailing backfill (CTB) compressive strength of the new material were studied. The heat transfer characteristics and endothermic effect of the PCM were simulated using Fluent software. The results showed the following: (1) The new paraffin–CaCl₂·6H₂O composite PCM improved the thermal conductivity of native paraffin while avoiding the water solubility of CaCl₂·6H₂O. (2) The calculation formula of the thermal conductivity of CaCl₂·6H₂O combined with paraffin was deduced, and the reasons were explained in principle. (3) The “enthalpy–mass scale model” was applied to calculate the phase change latent heat of nonreactive composite PCMs. (4) The addition of the paraffin–CaCl₂·6H₂O composite PCM reduced the CTB strength but increased its heat absorption capacity. This research can give a theoretical foundation for the use of heat storage backfill in green mines.