Thermal energy storage with Phase Change Materials (PCMs) is one of the most potential technologies for energy storage. However the low thermal conductivity of PCMs reduces the heat exchange rate during melting and solidification cycles. This paper studied the effects of two hybrid Carbon Nano-additives (CNs) fillers, that is, Expanded Graphite-Multi-walled Carbon Nano-tube (EG-MWCNT) and Expanded Graphite- Carbon Nano-fiber (EG-CNF), on the thermal conductivity of Paraffin-HDPE SSPCM. From the viewpoints of synergistic thermal enhancement effect and the interfacial thermal resistance, the principle of enhancing thermal conductivity of Paraffin-HDPE/EG-MWCNT and Paraffin-HDPE/EG-CNF composite PCMs was analyzed. A modified Maxwell-Garnett model with a synergy factor η was proposed, which found excellent agreement between model prediction and the experimental data. Compared with the 5 wt% loading of single CN additive EG, the thermal conductivities of hybrid CNs fillers (EG-MWCNT and EG-CNF) Paraffin-HDPE SSPCM had increased by 60% and 21.2% respectively. Within the scope of mass ratios of hybrid CNs fillers in this paper, Paraffin-HDPE/EG-MWCNT composite PCM exhibited superior performance than Paraffin-HDPE/EG-CNF in thermal conductivity with the optimal mass ratio of EG and MWCNT being 4:1.