In this study, iron oxide nanoparticles (α-Fe2O3) have been firstly used as a nucleating agent, which simultaneously reduces the supercooling degree of sodium acetate trihydrate (SAT) and improves its thermal conductivity. A series of SAT composite phase change materials (PCMs) for potential latent heat thermal energy storage applications were prepared by a ball milling method using carboxymethyl cellulose as a thickening agent and sodium dodecyl sulfonate as a dispersant. In order to investigate the effect of the mass ratio of α-Fe2O3 nanoparticles on the supercooling degree of SAT, various α-Fe2O3 contents (0.2, 0.4, 0.6, 0.8, and 1.0 mass%) were added into the SAT matrix. It was found that the supercooling degree of the SAT composite PCM was reduced to 0 °C at a α-Fe2O3 content of 0.8 mass%. Furthermore, no chemical reaction between SAT and α-Fe2O3 occurred, and the presence of α-Fe2O3 had no effect on the energy storage capability of SAT. The thermal conductivity of the SAT composite PCM was improved by 22.5% due to the addition of 0.8 mass% α-Fe2O3. After 60 melting–freezing cycles, the composite PCMs retained excellent stability with a small reduction in the phase change temperature (0.33 °C) and low latent heat loss rate (0.796%).