Palmitic acid (PA) is one of the main phase change materials (PCMs) for medium temperature thermal energy storage systems. In order to stabilize the shape and enhance the thermal conductivity of PA, the effects of adding nitrogen-doped graphene (NDG) as a carbon nanofiller were examined experimentally. NDG was dispersed in liquid PA at various mass fractions (1–5 wt%) using high power ultrasonication. The dropping point test shows that there was clearly no liquid leakage through the phase change process at the operating temperature range of the composite PCMs. The thermal stability and thermal properties of composite PCM were investigated with a thermogravimetric analyzer (TGA) and differential scanning calorimeter (DSC), respectively. The thermal conductivity of the PA/NDG composite was determined by the laser flash method. The thermal conductivity at 35 °C increased by more than 500% for the highest loading of NDG (5 wt%). The electrical conductivity of composite PCMs was increased significantly by using NDG. The thermal cycling test proved that the PA/NDG composites PCMs had good thermal reliability and chemical durability after 1000 cycles of melting and freezing. The thermal effusivity of the PA/NDG composite PCMs was larger than that of pure PA, which is advantageous for latent heat thermal energy storage (LHTES).