Widespread application of magnesium (Mg) has been prevented by its low strength and poor corrosion resistance. Core of this limitation is Mg’s low electrochemical potential and low solubility for most elements, favoring secondary phase precipitation acting as effective micro-galvanic elements. Mg-based metal–metal composites, while benefiting strength, are similarly active galvanic couples. We show that related detrimental corrosion susceptibility is overcome by nanoscale composite architecture design. Nanoscale phase spacings enable high-strength Mg–Fe composites with degradation rates as low as ultra-high purity Mg. Our concept thus fundamentally changes today’s understanding of Mg’s corrosion and significantly widens the property space of Mg-based materials.