Two time-dependent mathematical and numerical models with different levels of complexity and fidelity were developed to investigate the melting of a phase change material (PCM) configured as a number of aluminum-encased, PCM-filled slabs with embedded micro-channel aluminum tubes, and with parallel air-flow passages interposed between the slabs. Melting was first analyzed with the COMSOL Multiphysics finite-element model (FEM) in a 2-D domain representing a full-size slab. The melting process is simulated via the apparent heat capacity method. The model captures the effect of natural convection in the PCM melt as well as the conjugate heat transfer through the aluminum tubes. A fast-executing quasi 2-D reduced-order model (ROM) was developed for repetitive design optimization studies. The ROM relies on a time-dependent 1-D closed-form solution of the heat conduction equation in a melting PCM, coupled with variations of the air temperature and heat transfer coefficient. Consequently, the FEM results were employed to develop corrections to the ROM. The corrected ROM was then utilized to study the melting process in a multi-slab thermal storage device that is designed to freeze the PCM at night and release 500 W-h of cooling over a span of similar to 10 h during the day.