Analyses of natural behaviors of flexible underwater structures are necessary for designing flexible hydrofoils and propellers. The added mass and stiffness of hydrofoils and propellers have an influence on the natural frequencies of underwater structures. In the previous studies, only added mass was considered for the analysis. This resulted in an increase in the error of estimations of natural frequency at high speed conditions. Therefore, to predict the natural frequency variance of underwater structures, the added stiffness must be taken into account. In this paper, the added stiffness of underwater hydrofoils dependent on the flow speed is derived. The added stiffness is obtained from a change of the hydrodynamic force with structural displacement and is calculated for varying flow speeds. Hybrid FSI analyses of hydrofoils are performed by considering the added stiffness in the structural system of the FSI. The natural frequencies of the hydrofoil are compared with the experimental values. The results show that the flow speed–dependent added stiffness is required to accurately predict natural responses of underwater structures in high speed environment.