With the deep penetration of wind and photovoltaic power, the moment of inertia in the power system is reduced, resulting in the problem of frequency modulation for the automatic generation control of the power system. Energy storage is widely applied in the frequency modulation of power systems due to its fast reaction and accuracy. As a result, random simulation and empirical mode decomposition are combined to propose an energy storage capacity determination method in automatic generation control. Firstly, the empirical mode decomposition is utilized to decompose the regional control deviation into the high-frequency and low-frequency components. The energy storage frequency modulation is responsible for its high-frequency components, while traditional unit frequency modulation is in charge of its low-frequency components. Afterwards, the energy storage capacity is calculated via the high-frequency components of regional control deviation, and the energy storage is simulated considering the energy storage charge and discharge conditions. In the end, the frequency modulation effect is compared for the scenarios with different energy storage capacities and also without energy storage, and the energy storage capacity with the best frequency modulation effect is given consequently. The example simulation and results show that the proposed method is effective and feasible for obtaining the optimal energy storage capacity of automatic generation control in wind and solar power systems.