To study the effect of the metal matrix structure on the melting heat storage rate of PCMs, aluminum-alloy matrix/n-octadecane enhanced PCMs (phase change materials) were first fabricated using 3D printing technology. A melting heat storage experiment was then conducted in a circulating constant-temperature water bath to examine the influence of the metal matrix structure on the PCM melting process. Finally, a numerical model for the melting heat storage of enhanced PCMs accounting for liquid-phase flow was developed based on the effective heat capacity method and fluid-solid-thermal coupling principles. The model was validated against experimental results, and subsequently used to systematically analyze the effects of matrix configuration, wall thickness and materials on the melting heat storage rate, optimize the matrix configuration ultimately. Results show that encapsulating PCMs in a metal matrix changes the melting heat storage pattern from single-sided melting to simultaneous four-sided melting. For five metal matrix configurations (1×1 to 5×5 arrays), the melting heat storage rate first decreases and then increases as the array number increases. The 3×3 configuration exhibits the lowest melting heat storage rate due to significant suppression of liquid-phase natural convection. The enhancement critical wall thickness of the metal matrix is determined to be 0.354 mm. When the wall thickness increases from 0.4 mm to 1.6 mm, the melting heat storage rate improves by 169%. Optimizing the 4×4 matrix into a vertically penetrating 4×1 design eliminates the suppression of liquid-phase natural convection, boosting the melting heat storage rate by 319.5% and achieving the best enhancement effect of the metal matrix structure.