Passive latent energy storage technologies with Phase Change Materials (PCM) provide a potential solution to reduce energy demand and regulate thermal comfort in occupied buildings. However, leakage of liquid PCM and low thermal conductivity limit the PCM building applications. In this context, the objective of this study is to develop a new shape stable PCM enhanced by carbon-based nanoparticles. The paraffin, Low-Density Polythene (LDPE) and Multi-Walled Carbon Nano-Tube (MWCNT) are used as PCM, supporting matrix and thermal conductivity enhancer, respectively. The PCM composites with different ratios were prepared by melt blending method, using a parallel co-rotating twin-screw micro-extruder. A series of experimental tests were achieved. Thermophysical and chemical analyses (Modulated Differential Scanning Calorimetry (MDSC), Thermogravimetric Analysis (TGA), thermal conductivity, Fourier Transform Infrared Spectroscopy (FTIR)) were carried out to characterize the raw materials and the prepared PCM composites, to optimize the energetic and phenomenological behaviors of samples. The results indicate a good chemical and physical compatibility of the prepared samples. Besides, the LDPE maintains the molten paraffin in compact shape during the solid-liquid transition. Thus, paraffin-LDPE-MWCNT with 70-29-1 wt.% exhibit the best thermal properties with a latent heat of 93 J/g. 1 wt.% of MWCNT improves the thermal conductivity of paraffin-LDPE by 28%. The results of this study demonstrate a significant potential of the prepared shape stable PCM to improve the thermal inertia of construction materials and thermal comfort inside buildings.