This work concerns the development of a shape-stable molten salt based composite phase change material (PCM) for low and medium temperature thermal energy storage. The composite is fabricated by using a cold compression and hot sintering method with the employment of a eutectic quinary nitrate salt of NaNO3-NaNO2-KNO3-KNO2-LiNO3 as PCM, halloysite nanotube (HNT) as skeleton supporting material and natural graphite as thermal conductivity enhancement additive. A sequence of characterizations is performed to investigate the composite microstructure, chemical and physical compatibility, thermal stability, phase change behaviour, and thermal conductivity as well as cycling performance. The results indicate that an excellent chemical compatibility has been achieved among the ingredients of quinary salt, HNT and graphite within the composite. A mass concentration of 50 wt% HNT endows the composite with the optimal formulation in which 10 wt% graphite can be successfully accommodated and a thermal conductivity around 1.31 W/m·K can be acquired. Moreover, in such a formulation, the composite presents a considerably low melting temperature of 72.4 °C and a high thermal decomposition temperature of 530 °C, which achieves the composite a relatively high energy storage density nearly 500 kJ/kg at a temperature range of 25–510 °C. The results presented in this work demonstrate that the quinary salt-HNT-graphite composite with fairly low phase transition temperature and a splendid combination of thermal properties and cycling performance could be a promising candidate to replace the conventional organic based PCMs utilized in low temperature thermal energy storage fields.