This article discusses cyclic hardening and fatigue behaviors of stainless steel 304L, the behavior of which is greatly influenced by prior loading. Effects of loading sequence, mean strain and mean stress, and pre-straining (PS) were investigated using constant amplitude as well as step and random loading tests. Contrary to common expectations, fatigue lives in strain-controlled mean strain tests were significantly affected by the mean strain, in spite of mean stress relaxation. PS induced considerable hardening and led to different results on fatigue life, depending on the test control mode. Secondary hardening was observed in some tests, characterized by a continuous increase in the stress response. Possible mechanisms for this behavior are also discussed. To correlate fatigue life data of a material such as stainless steel with strong deformation history effect, it is shown that a damage parameter with both stress and strain is required. The Fatemi-Socie (FS) parameter as such a parameter is shown to correlate the data under different control modes and loading conditions.