Purpose: Applications for highly corrosive environments and cyclic loading are often made out of austenitic stainless steels. Corrosion fatigue and crack propagation behaviour has been studied to determine failure processes and damage mechanisms. Approach: CrNiMo stabilized austenitic stainless steel and CrMnN austenitic stainless steel in solution annealed and cold worked condition are compared. S/N curves and crack propagation rate curves are recorded in 43 wt% CaCl2 solution at 120 °C, which resembles most severe potential service conditions. For comparison these experiments are also performed in inert glycerine. Additionally, the electrochemical behaviour of these materials has been studied. Findings: The CrMnN steels have excellent mechanical properties but are very susceptible to stress corrosion cracking in the test solution. The fatigue limit as well as the threshold for long crack growth are significantly reduced in corrosive environment. Moreover these steels exhibit a remarkable increase in the propagation rate, which is extremely pronounced in the near threshold region. This effect is enhanced by cold working. CrNiMo steels also show a reduction in the fatigue limit, but it is less pronounced compared to CrMnN steels. The threshold is significantly reduced in corrosive environment, but propagation rate is lower in corrosive environment compared to inert glycerine. Possible explanations of this surprising behaviour are discussed.