Abstract: In weakly ferromagnetic materials, already small changes in the atomic configuration triggered by temperature or chemistry can alter the magnetic interactions responsible for the non-random atomic-spin orientation. Different magnetic states, in turn, can give rise to substantially different macroscopic properties. A classical example is iron, which exhibits a great variety of properties as one gradually removes the magnetic long-range order by raising the temperature towards and beyond its Curie point of $T_{\text{C}}^{0}=1043$\,K. Using first-principles theory, here we demonstrate that uniaxial tensile strain can also destabilize the magnetic order in iron and eventually lead to a ferromagnetic to paramagnetic transition at temperatures far below $T_{\text{C}}^{0}$. In consequence, the intrinsic strength of the ideal single-crystal body-centered cubic iron dramatically weakens above a critical temperature of $\sim 500$\,K. The discovered strain-induced magneto-mechanical softening provides a plausible atomic-level mechanism behind the observed drop of the measured strength of Fe whiskers around $300-500$\,K. Alloying additions which have the capability to partially restore the magnetic order in the strained Fe lattice, push the critical temperature for the strength-softening scenario towards the magnetic transition temperature of the undeformed lattice. This can result in a surprisingly large alloying-driven strengthening effect at high temperature as illustrated here in the case of Fe-Co alloy.