Abstract: With the large-scale integration of uncertain renewable energy sources into power systems, the frequency stability of the power system is facing severe challenges. Reasonable planning of the energy storage is an important means for maintaining the stable operation of the power system and coping with the uncertainty of renewable energy sources. Therefore, focusing on the planning problem of the energy storage capacity for the power system with high renewable energy penetration, a distributed robust planning for the energy storage capacity is proposed while providing frequency support by the multi-energy complementarity. Firstly, a frequency safety model with frequency support provided by the multi-energy complementarity is established, which is then linearized and embedded into the typical daily operation to maintain the frequency stability of the power system. Secondly, the distributed robust optimization based on the generative adversarial network is adopted to achieve the energy storage capacity planning under the worst probability distribution of the new energy output and to deal with the uncertainty of the new energy output. Finally, simulation with the IEEE39 node system verifies that the proposed method is able to ensure the frequency security of the power system and possess a good economy and robustness.