Industrial low-temperature freezing applications are often batch processes, requiring a lot of energy, exerting stress on the electrical grid. To relieve this stress, thermal energy storage can be used. However, there is a lack of suitable storage material for low temperature applications (around −50 °C). Under high pressures, carbon dioxide can be used as the phase change material for storage temperatures around −55 °C. In this study, a parametric study was conducted on the design and operational parameters of an industrial-scale pillow plate heat exchanger with carbon dioxide. Two responses were selected for the analysis where R1 considered the storage size over the phase change time (kWh/h), while R2 indicated the cost over the storage size (USD/kWh). Using design of experiments, a total of 52 simulations were carried out to investigate the parameters under constant heat transfer surface area. Analysis of variance was then carried out followed by correlation development and optimization. It was found that regardless of the process (charging or discharging), for R1 and R2, the difference between refrigerant and carbon dioxide phase change temperatures followed by plate material had the highest significance. In contrast, the refrigerant flow rate had the lowest significance in almost all cases. Moreover, considering an equal weight for the responses, overall optimal conditions were determined for the processes. The recommended values for plate pitch, plate material, difference between refrigerant and carbon dioxide phase change temperatures and refrigerant flow rate were 25 mm, aluminum, 15 °C and 4 kg/s, respectively.