Due to the significant differences in the formation temperature and crystal structure between the primary α-Mg and eutectic β-Mg₁₇Al₁₂, it is a great challenge to achieve simultaneous refinement of the primary and eutectic phases in Mg-Al based alloys via heterogeneous nucleation. Surprisingly, we found that the α-Mg and β-Mg₁₇Al₁₂ in the AZ80 alloy can be simultaneously refined after 0.2 wt.% Sm addition, with the grain size decreasing from ∼217 ± 15 µm to ∼170 ± 10 µm and the β-Mg₁₇Al₁₂ morphology changing from a typical continuous network to a nod-like or spherical structure. The simultaneous refinement mechanism is investigated through solidification simulation, transmission electron microscopy (TEM), and differential thermal analysis (DTA). In the AZ80-0.2Sm alloy, many Al₈Mn₄Sm particles can be observed near the center of the α-Mg grains or inside the β-Mg₁₇Al₁₂. Crystallographic calculations further reveal that the Al₈Mn₄Sm has good crystallographic matching with both the α-Mg and β-Mg₁₇Al₁₂, so it possesses the potency to serve as heterogeneous nucleation sites for both phases. The promoted heterogeneous nucleation on the Al₈Mn₄Sm decreases the undercooling required by the nucleation of the primary and eutectic phases, which enhances the heterogeneous nucleation rate, thus causing the simultaneous refinement of the α-Mg and β-Mg₁₇Al₁₂. The orientation relationships between the Al₈Mn₄Sm and Mg/Mg₁₇Al₁₂ are identified, which are [1210]_Mg//[010]_Al8Mn4Sm, (1010)_Mg//(301)_Al8Mn4Sm and [112]_Mg17Al12//[010]_Al8Mn4Sm, (110)_Mg17Al12//(301)_Al8Mn4Sm, respectively. Furthermore, the refinement of the β-Mg₁₇Al₁₂ accelerates its dissolution during the solution treatment, which is beneficial for cost saving in industrial applications. Other Al₈Mn₄RE compounds such as Al₈Mn₄Y might have the same positive effect on the simultaneous refinement due to the similar physicochemical properties of rare earth elements. This work not only proves the possibility of simultaneously refining the primary and eutectic phases in Mg-Al based alloys via heterogeneous nucleation, but also provides new insights into the development of refiners for cast Mg alloys.