In the industrial sector, a large amount of energy is released at low temperatures, between 0 and 200 °C. To improve the overall energy efficiency of these processes, it is possible to recover this waste heat. The technology of thermal energy storage by Phase Change Materials (PCM) has appeared as one of the most economically viable methods for recovering waste heat. The PCM presents both a significant storage density and the possibility of energy restitution at a stable temperature. However, the low thermal conductivity of PCMs, specifically paraffins, limits its large-scale application. In this context, this study investigates the effect of the fins on the PCM regenerator behaviour. For that, a parametric study of the fins' number, length, thickness, and position is conducted. The volume occupied by the PCM was constant to keep the same energy density. The PCM's melting and solidification processes in a horizontal coaxial heat exchanger were numerically investigated using ANSYS Fluent commercial software. Paraffin wax with a melting point of 55 °C was used as PCM. The numerical study shows that the addition of longitudinal fins improves the apparent conductivity considerably and consequently reduces the melting time by up to 61%. The optimal configuration found in this study: fin number N = 4, dimensionless thickness = 0.1, dimensionless height = 0.9, and unevenly distributed fins. This configuration achieves a shorter time in completing the charging/discharging cycle of the PCM and allows a time saving of 21%.