In recent years, a new class of metallic materials featuring heterogeneous structures has emerged. These materials consist of distinct soft and hard domains with significant differences in mechanical properties, allowing them to maintain high strength while offering superior ductility. Magnesium (Mg) alloys, renowned for their low density, high specific strength, exceptional vibration damping, and electromagnetic shielding properties, exhibit tremendous potential as lightweight and functional materials. Despite their advantageous properties, high-strength Mg alloys often suffer from limited ductility. However, the emergence of heterogeneous materials provides a fresh perspective for the development of Mg alloys with both high strength and ductility. This article provided a fundamental overview of heterostructured materials and systematically reviewed the recent research progress in the design of Mg alloys with strength-ductility balance based on heterostructure principles. The review encompassed various aspects, including preparation methods, formation mechanisms of diverse heterostructures, and mechanical properties, both within domestic and international contexts. On this basis, the article discussed the challenges encountered in the design and fabrication of heterostructured Mg alloys, as well as the urgent issues that require attention and resolution in the future.