Using first-principles theories, we demonstrate that the elastic properties of substitutional disordered Fe-rich Fe-Cr-Ni alloys (austenitic stainless steels) sensitively depend on their magnetic state. Due to the strong magnetoelastic effects in paramagnetic Fe0.70Cr0.15Ni0.15 alloy, the room-temperature magnetism is found to alter the usually dominating chemical effects and give a large anomalous contribution to the temperature dependence of the elastic constants.