Manganese is added to many magnesium alloys to control impurity iron, but its effects on phase transformations and microstructure formation remain incompletely understood. Here we show that an Al-Mn-based decagonal quasicrystal (d-QC) forms in the late stages of solidification in AZ31 and AZ91 magnesium alloys at relatively slow cooling rates, here down to 0.1 K/s. The d-QC has a periodicity of ∼ 12 Å, grew as decagonal rods and commonly shared interfaces with Al8Mn5 and eutectic Mg17Al12. A reproducible orientation relationship (OR) was measured with Al8Mn5 only, indicating that the d-QC nucleated on Al8Mn5. The OR is consistent with the structural relationship between quasicrystals and gamma brasses and gives the d-QC nucleation advantages over LT-Al11Mn4 during solidification. A subsequent heat treatment at 410 °C caused both Al8Mn5 and the d-QC to transform into LT-Al11Mn4.