Thermal energy storage (TES) systems using phase change materials (PCMs) are of increasing interest for more efficient energy utilization. Herein, sodium sulfate decahydrate (Na2SO4·10H2O; SSD)/nanofibrillated cellulose (NFC)/graphite PCM composites were prepared by a simple blending method. NFC and graphite were used to improve the performance of SSD-based PCMs by mitigating the phase separation and low thermal conductivity issues. The phase stability, thermal, and structural properties of the prepared PCM composites were investigated. The role of NFC was to thicken and thereby improve phase stability, and to assist dispersion of hydrophobic graphite without aggregation by leveraging its amphiphilic characteristics. The supercooling degree, melting temperature, and enthalpy of 4.2 °C, 31.1 °C, and 121.7 J/g, respectively, were measured for the PCM containing 5 wt% of graphite. Fourier transform-infrared spectroscopy and X-ray diffraction studies indicated that no chemical reactions occurred between the PCM components. The thermal conductivity was enhanced by 250 % when 5 wt% of graphite was added, which improved heat charging during the melting process. Increased hydrogen bonding between fibrils and water molecules enhanced the thermal stability by suppressing water evaporation. Our results indicate that the composite would be an efficient TES system.