Abstract Thermal energy storage (TES) using phase change materials (PCMs) is being widely considered as one of the alternative solutions for effective use of solar energy. This paper presents a multi-objective optimisation strategy for TES systems using PCMs for solar air systems, in which two performance indicators of average heat transfer effectiveness and effective PCM charging time were used as the conflicting objectives. The influence of the key design variables on the performance of an air-based PCM TES system was first experimentally investigated using Taguchi method, and the results were used to develop two performance models for optimisation. A genetic algorithm was used to search for an optimal Pareto front and a multi-criteria decision-making process was employed to determine the compromise optimal solutions. The results showed that the average heat transfer effectiveness of the PCM TES system can be improved from 44.25 to 59.29% while the effective PCM charging time increased from 4.53 to 6.11 h when using the solutions identified by the proposed strategy with the weighting factors of 0.5/0.5 for both objectives, in comparison to a baseline case. A further comparison showed that the optimal design identified by the proposed strategy outperformed the two designs identified using Taguchi method.