The integration of thermal energy storage systems (TES) in waste-heat recovery applications shows great potential for energy efficiency improvement. In this study, a 2D mathematical model is formulated to analyze the performance of a two-tank thermochemical heat storage system using metal hydrides pair (Mg2Ni/LaNi5), for high-temperature waste heat recovery. Moreover, the system integrates a phase change material (PCM) to store and restore the heat of reaction of LaNi5. The effects of key properties of the PCM on the dynamics of the heat storage system were analyzed. Then, the TES was optimized using a genetic algorithm-based multi-objective optimization tool (NSGA-II), to maximize the power density, the energy density and storage efficiency simultaneously. The results indicate that the melting point Tm and the effective thermal conductivity of the PCM greatly affect the energy storage density and power output. For the range of melting point Tm = 30–50 °C used in this study, it was shown that a PCM with Tm = 47–49 °C leads to a maximum heat storage performance. Indeed, at that melting point narrow range, the thermodynamic driving force of reaction between metal hydrides during the heat charging and discharging processes is almost equal. The increase in the effective thermal conductivity by the addition of graphite brings about a tradeoff between increasing power output and decreasing the energy storage density. Finally, the hysteresis behavior (the difference between the melting and freezing point) only negatively impacts energy storage and power density during the heat discharging process by up to 9%. This study paves the way for the selection of PCMs for such combined thermochemical-latent heat storage systems.