Various properties of the paraffin have made them compatible to be incorporated in the building materials for improving the latent heat storage capacity of the building envelope. However, the poor thermal conductivity of the paraffin reduces their thermal performance and hence limits their direct application/incorporation in the buildings. In this study, composite mixtures of paraffin and expanded perlite (EP) with an equal weight percent of 49.5 and 47.5, loaded with 1% and 5% of graphene nano-platelets, respectively, were synthesized. The developed samples were characterized uncycled and after 2000 thermal cycles. The results indicate that phase change material (PCM)/expanded perlite/graphene nano-platelets composite shows a significant increment in the thermal conductivity, reduction in the latent heat storage capacity, and a small weight loss. The heat storage/release test depicts that the phase change material/expanded perlite/graphene nano-platelets-5 shows 1.66 and 2.5 times faster heat storage/release rate than phase change material/expanded perlite/graphene nano-platelets-1 and paraffin, respectively. There is no significant change noted after 2000 thermal cycles in phase change material/expanded perlite/graphene nano-platelets-5 and phase change material/expanded perlite/graphene nano-platelets-1 samples, suggesting long-term reliability of the composite PCM. Additionally, thermogravimetric analysis (TGA) and Fourier-transform infrared spectroscopy (FTIR) testing were also conducted and the results suggest high thermal reliability and good chemical compatibility. These analyses suggest that the phase change material/expanded perlite/graphene nano-platelets composite can become a potential candidate for thermal energy storage.