Phase change material (PCM) is a commonly used energy-storage media in thermal storage devices, and the shell-and-tube latent heat storage unit is one of the widely applied thermal storage devices. Currently, most research on this type of thermal storage device focuses on single temperature boundary conditions, and research on the thermal storage performance of phase change thermal storage devices under multiple temperature boundaries is relatively scarce. To this end, a double-tube shell-and-tube latent heat storage model featuring dual temperature boundaries was developed, and numerical simulations of the heat-storage process were conducted using the COMSOL Multiphysics software. The results show that, under a constant temperature difference between the upper and lower heating tubes, altering their vertical arrangement can significantly enhance the melting rate of the PCM and improve thermal-storage efficiency. The temperature difference between the heating tubes has a pronounced effect on the complete melting time, although the total stored energy varies only slightly under the same temperature difference. Moreover, the influence of tube spacing on melting time differs depending on the tube-arrangement conditions. A comparative analysis between natural-convection and pure-conduction models was also carried out. In the pure-conduction model, the melting-time difference between the two heating-tube arrangements is relatively small. However, in the natural-convection model, the configuration with the upper tube at a lower temperature and the lower tube at a higher temperature exhibits a more significant convection-enhancement effect. As tube spacing increases, the natural-convection enhancement coefficient for the “top low-bottom high(TL-BH)” temperature arrangement is clearly superior to that of the “TL-BH” arrangement. The research results offer new insights for the design and optimization of phase-change heat storage units under multi-temperature-boundary conditions and provides theoretical support for identifying melting mechanisms.