Common phase change materials (PCMs) possess very low thermal conductivity whilst hybrid PCM with graphene filler could be produced to achieve increased thermal conductivity. This research focuses on the effects of graphene flakes on the thermal conductivity of a PCM (paraffin wax). Three experimental parameters at different levels of average lateral sizes of graphene flakes (4.5, 5 and 7µm), mass fractions (0.1, 0.2 and 0.25 wt.%), and rising temperatures (25-75°C) are considered. For the first time in the literature, the impact of various parameters on the thermal conductivity performance of the nanoPCM-based graphene nano-composites is investigated extensively by adopting response surface methodology supported by central composite design. Thermal conductivity prediction is proposed by a new general correlation and a promising value of the coefficient of determination (R2) higher than 0.88. Amongst the investigated various variables in terms of impact on thermal conductivity, the temperature is identified as the most influential parameter on response variables. According to the implemented optimization technique, for the composite with the average graphene flake size of 4.5 µm, the optimum value of the thermal conductivity is found 0.275 W/m K at the mass fraction of 0.186 wt.% and temperature of 69.73°C.