The low thermal conductivity of phase change materials (PCMs) remains the main challenge for their widespread application in latent heat thermal energy storage systems. In the present study, the effect of curved-shaped fins on improving the melting rate of RT35 PCM in a triple-tube heat exchanger is numerically and two-dimensionally investigated. Simulations are performed using ANSYS Fluent CFD software employing the enthalpy-porosity method. The effects of two key parameters—the number of linear fins (3, 4, and 5) and fin geometry (linear, parabolic, and radial)—on liquid fraction, temperature distribution, and velocity field during the melting process are studied. The results demonstrate that increasing the number of linear fins from 3 to 5 enhances the liquid fraction by 27% and 41% at 600 seconds, respectively, and improves the PCM temperature by up to 15 K. Comparing different fin shapes reveals that parabolic and radial fins increase the liquid fraction by 13% compared to the linear configuration at 400 seconds. Moreover, the complete melting time in the five-fin parabolic configuration decreases by 50% compared to the five-fin linear case and by 68% compared to the three-fin linear case. Overall, fins with greater curvature exhibit superior thermal performance due to enhanced buoyancy forces and improved natural convection flow. The findings of this research can be utilized in the optimal design of thermal energy storage heat exchangers for applications in air conditioning systems, solar collectors, and industrial waste heat recovery.