Heating and cooling systems in building infrastructure utilize conventional materials that account for a considerable amount of energy usage and waste. Phase change material (PCM) is considered a promising candidate for thermal energy storage that can improve energy efficiency in building systems. Here, a novel salt hydrate-based PCM composite with high energy storage capacity, relatively higher thermal conductivity, and excellent thermal cycling stability was designed and developed. The thermal cycling stability of the PCM composite was enhanced by using dextran sulfate sodium (DSS) salt as a polyelectrolyte additive, which significantly reduced the phase segregation of salt hydrate. The energy storage capacity and the thermal conductivity of the composite were enhanced by the addition of various graphitic materials along with Borax nucleator. A significant increase in thermal cycling stability was observed for the DSS-modified composite, with over 100 thermal cycles without degradation. The final PCM composite exhibited as much as 290% increase in energy storage capacity relative to the pure salt hydrate, and approximately 20% increase in thermal conductivity. In addition, the PCM composite developed can be produced at larger scale, and can potentially change the future of heating/cooling system in building infrastructure.