Thermal energy storage (TES) has attracted intense attention because of its positive contribution to sustainable energy utilization. To improve the TES performance of sodium acetate trihydrate (SAT), the combined use of cellulose nanofibril (CNF) and graphene nanoplatelet (GNP) was investigated to tackle the phase separation problem and to improve the thermal conductivity of SAT. Phase stability and rheology tests revealed that adding 0.8% of CNF to SAT increased viscosity, enhanced solid-like rheological behavior, and successfully eliminated phase separation. Meanwhile, the amphiphilicity of CNF facilitated the dispersion of GNP. Sodium phosphate dibasic dodecahydrate (DSP; Na 2HPO 4·12H 2O) was selected as the nucleating agent, which reduced the supercooling degree of SAT to 2.1 °C. Phase change materials (PCMs) were prepared by simply blending GNP pre-dispersed with CNF, DSP, and SAT. Due to the excellent thermal performance of GNP and its good dispersion by CNF, the prepared PCM composites showed enhanced thermal conductivity compared with that of pure SAT. Thermal reliability testing indicated that the melting point and enthalpy of the prepared PCM composites decreased after 100 melting/freezing cycles. Overall, PCM composites with enhanced performance were fabricated based on renewable, bio-based, and biodegradable nanocellulose. These composites can be used for certain TES applications.