This paper presents a general procedure to optimize the design of a PCM storage tank, including the specification of design objectives, the identification of decision variables (for optimization), the construction of computer simulation platform and the final decision making. The general procedure was demonstrated by applying it to an open-air swimming pool, where the design objective was to minimize the volume of the PCM storage tank when it was required to enable heat storing to maintain the water temperature of an open-air swimming pool inside the thermal comfortable range during its open period in winter season. After identifying decision variables, a computer simulation platform was developed using TRNSYS and MATLAB to investigate the effects of the decision variables on the volume of the PCM storage tank. Case studies show that the proposed optimization is able to efficiently reduce the volume of the PCM storage tank without sacrificing the thermal storage capacity. Therefore, this study provides useful guidelines to optimize the design of a PCM storage tank.