Owing to their flexible structure and tailorable thermochemical properties by changing A- and B-site dopants and compositions, perovskite oxides provide great tunability for various applications such as thermochemical energy storage (TCES). We present a high-throughput combinatorial approach that systematically optimizes and designs perovskite oxides for TCES. We used a high-throughput density functional theory (DFT) model to perform thermodynamic-based calculations on over 2000 A- and/or B-site doped SrFeO3-δ perovskite oxides. Based on the results of DFT calculations, we selected 61 candidates to optimize critical TCES parameters such as redox oxygen capacity and reaction enthalpy. We also conducted experimental measurements to determine the thermodynamic properties of 45 samples with pure perovskite phases. Many of these materials exhibited promising TCES performance. Particularly, Sr0.125Ca0.875Fe0.25Mn0.75O3-δ achieved the largest energy storage density of 894 kJ/kgABO3 under the operating conditions of 400 oC/0.2 atm O2 and 1100 oC/Ar. By utilizing both experimental and computational results, we developed an improved screening approach to accelerate the optimization of perovskites for TCES. Through the improved screening approach, we predicted reaction enthalpy within 25.4% deviation and redox oxygen capacity with a correlation coefficient of 0.64. Additionally, we utilized this approach for the selection of perovskite oxides to be used in a novel composite material that combines TCES with the latent heat storage from the phase change of eutectic molten salts.