Widespread commercialization of PCM-based latent heat storage systems is limited by the low melting and solidification rates during the phase transition process. In this study, fins are used to enhance the phase change process. A parametric study is conducted to understand the effect of fins on the thermal performance of vertically- and horizontally-oriented rectangular storage tanks. Throughout simulations, the fin volume, and thereby the mass of PCM in the tank, were kept constant. It was observed that the horizontal enclosures can take advantage of the development of strong natural convection flow until near the end of the melting process, whereas with vertical counterparts the strength of the convection currents was diminished during the shrinkage stage. The results suggest that longer and thinner fins are more beneficial for enhancing the melting rate than shorter and thicker fins. It was concluded that for horizontal enclosures with fin lengths of 25 and 35 mm, increasing the number of fins does not necessarily shorten the melting time. The maximum melting time reduction compared to the 3-fin vertical enclosure with a fin length of 25 mm (chosen as our benchmark case) was 75.1% when nine 45-mm-long fins are used in a horizontal enclosure.