Latent heat storage (LHS) technologies adopting phase change materials (PCMs) are increasingly being used to bridge the spatiotemporal mismatch between energy production and demand, especially in industries like solar power, where strong cyclic fluctuations exist. The shell-and-tube configuration is among the most prevalent ones in LHS and thus draws special attention from researchers. This paper presents numerical investigations on the melting of PCM, a paraffin blend RT27, inside a horizontal annulus. The volume of fluid model was adopted to permit density changes with the solidification/melting model wherein natural convection was taken into account. The eccentricity and diameter of the inner tube, sub-cooling degree of the PCM, and the heating-surface temperature were considered as variables for study. Through the evaluation of the melting time and exergy efficiency, the optimal parameters of the horizontal annulus were obtained. The results showed that the higher the heating boundary temperature, the earlier the convection appeared and the shorter the melting time. Also, the different eccentricity and diameters of the inner tube influenced the annulus tube interior temperature distribution, which in turn determined the strength and distribution of the resulting natural convection, resulting in varying melting rates.