The latent heat thermal storage using Phase Change Materials (PCMs) is one of the essential aspects to be addressed for rapid expansion of utilisation of Renewable Energy sources and waste heat. The major disadvantage of PCMs, deployed in such thermal storage systems, is their low thermal conductivity and, in some cases, low latent heat. Paraffin wax/expanded graphite (PW/EG) composite PCMs with the EG mass fraction of 2%, 4%, and 6% were prepared by absorption of molten organic material into the EG structure. FireCarb TEG-315 and FireCarb TEG-160 were used as EG of A- and B-type, respectively, and PW 53–57 °C was deployed as the PCM in this study. Polarizing optical microscope, scanning electron microscopes and Fourier transform infrared spectroscopy were used to characterize the structure of composite PCMs. Thermal properties of pure Paraffin and produced composite materials were determined using a differential scanning calorimeter and thermal conductivity analyser. One of originalities of this work is that the statistical method of assessment of heterogeneity in composite PCMs was proposed for the first time with the use of Matlab software. This method was deployed for the quantitative assessment of uniformity of the EG distribution in composite PCMs structure. The novelty of obtained results is in detection of intermolecular interaction between B-type EG and PW. This interaction further enhances thermo-physical properties of the PW/EG composites. In contrast to pure PW and PW/A-type EG composite PCMs, in which the solid-solid transition and solid-liquid phase change are observed, PW/B-type EG compositions exhibit only the solid-liquid phase change. The heat storage capacity in both types of compositions was found to be almost identical. Despite of prolonged sample's ultrasonic treatment, the structure of PCM compositions was found to be far from being homogeneous. However, the thermal conductivity of compositions with 6 wt % of EG was determined to be 0.977 W/m°C for the PCM with A-type EG and 1.263 W/m°C for the PCM with B-type EG in comparison with the value of 0.258 W/m°C for pure PW. These values of the thermal conductivity correspond to the enhancement ratios of 3.79 and 4.9, respectively. If uniformity in the EG distribution in PW can be improved, then the thermal conductivity of composite PCMs would also considerably increase. Findings of this work are being used for designing a cost efficient solar thermal storage system with the reduced charging/discharging times as a part of an international project funded by EC.