The paper contains results of tests on fatigue strength under uniaxial random loading and cavitation erosion resistance for three steels: 10HNAP, 18G2A and 15G2ANb. The obtained fatigue and cavitation characteristics were used for determination of relations between these two phenomena. From the analysis it appears that there is correlation between fatigue strength of the material under random loading and its cavitation erosion resistance. It has been shown that fatigue tests under random loading and tests on cavitation erosion of 10HNAP, 18G2A and 15G2ANb steels may be described with a mathematical model of the same type. It has been also found that there is a linear relation, in the dual logarithmic system, between cavitation erosion resistance of the steels tested and their fatigue strength under random tension—compression with zero mean value.