Using ab initio alloy theory, we determine the elastic parameters of ferromagnetic and paramagnetic Fe(1-c)Cr(c) (0 ≤ c ≤ 1) alloys in the body centered cubic crystallographic phase. Comparison with the experimental data demonstrates that the employed theoretical approach accurately describes the observed composition dependence of the polycrystalline elastic moduli. The predicted single-crystal elastic constants follow complex anomalous trends, which are shown to originate from the interplay between magnetic and chemical effects. The nonmonotonic composition dependence of the elastic parameters has marked implications on the micro-mechanical properties of ferrite stainless steels.