The attractive properties of Mg-bcc nanocomposites have gained increasing interest, but fabrication to bulk scales failed so far as strain immediately localizes within the Mg-phase. Targeting successful processing strategies, we analyze the deformation behavior and resulting microstructures of Mg-Fe composites as a function of applied strain and processing temperature using high-pressure torsion. Counterintuitively, processing at 73% of Mg's melting point accelerated microstructural refinement and improved homogeneity. Suppressing strain localization of the phases, a three-fold hardness increase compared to ambient processing is obtained. Such hardness levels suggest that further optimization likely paves the way towards bulk Mg-based materials beyond a gigapascal strength.