The fatigue behavior of austenitic stainless steels and nonmagnetic high-manganese steels has been investigated in ambient air, liquid nitrogen, and liquid helium. Particular attention was paid to the influence of nitrogen and carbon additions. Low-cyclic fatigue tests were carried out under tension-compression at a strain rate of 3 × 10−3 s−1. In all the stainless steels, cyclic softening following initial hardening was observed at lower strain amplitudes; the softening was remarkably enhanced by the addition of nitrogen. Solute carbon also had a similar effect, although to a lesser degree than nitrogen. In the high-manganese steels, the amount of softening was significantly affected by manganese content. The effect of the interstitial atoms on the softening was smaller in the 32% manganese series of steels than in the stainless steels. A decrease in the testing temperature increased the softening in both series of steels. Planar structures or less-tangled structures of dislocations were formed, and cellular structures were scarcely observed in all the steels showing the remarkable softening. The tendency of dislocations to form these less-tangled dislocation arrangements, and the softening and hardening behavior of the steels, could not be explained as an effect of stacking fault energy alone, but could be qualitatively interpreted by assuming the existence of some ordering between substitutional and interstitial atoms in the as-solution-treated steels. The significant softening seemed to increase fatigue life under the strain-controlled condition.