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 its Curie point of TC°= 1043 K. Using first-principles theory, here we demonstrate that uniaxial tensile strain can also destabilise the magnetic order in iron and eventually lead to a ferromagnetic to paramagnetic transition at temperatures far below TC°. In consequence, the intrinsic strength of the ideal single-crystal body-centred cubic iron dramatically weakens above a critical temperature of ~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.