The effects of cycle frequency on the fatigue strength of carbon steels under simultaneous corrosion in tap water and saline are studied. The stress σ_c given under corrosion fatigue increases to σ_ck owing to the notch effect of corrosion pits. At a certain repetition number of N, σ_ck reaches the fatigue strength σ of the same repetition number in air and fractures by corrosion fatigue occur. And the condition of fracture is given by Eq. (5), under consideration that the corrosion effect k increases with time and σ is a function of N alone. Various experimental results are well explained by this criterion. This conception is further extended to the corrosion fatigue combining the static pre-corrosion and also changing cycle frequencies during runs. For the corrosion fatigue under varying stress amplitudes the cumulative damage criterion was found to be applicable. And so the strengths of corrosion fatigue under wide stress conditions may be known.