It is well known that the soil-structure interaction (SSI) changes the dynamic response of a structure supported on flexible soil. The analysis of optimally controlled SSI systems has certain difficulties due to the nature of the SSI and the optimal control problem. In this paper, a two-step iteration-based numerical algorithm is proposed to handle optimally controlled SSI systems under earthquakes. First, the optimal control forces are obtained by using a fixed-base system. Then, the optimal control forces are converted to the frequency domain by the Fourier transform technique to be used in the equations of the SSI system. The lateral displacement and the rocking of the foundation are obtained from the equations of the SSI system containing the optimal control forces in the frequency domain. The lateral displacement and rocking of the foundation are then converted to the time domain by the inverse Fourier transform technique, and the lateral accelerations and the rocking accelerations of the foundation are obtained by the forward finite difference method. During the second step, the optimal control forces are calculated again by using the lateral acceleration and the rocking acceleration of the foundation along with the earthquake ground motion. Using the method explained above, the optimal control forces obtained in the time domain are used in the equations of the soil-structure system from which the behavior of foundation and structure is obtained. In the final section of the paper, a numerical study is conducted for a controlled structure supported on flexible soil.