In this work, AZ61 magnesium alloy coated with NiCrAl intermediate layer with outer of Fe-based amorphous coating was fabricated by high-velocity oxy-fuel thermally spraying. Through the intermediate metallic coating, the traditional mismatch of Fe-based materials and magnesium substrate was overcome, exhibiting good metallurgical bonding in the interface regions. The protective magnesium alloy with Fe-based amorphous coating possesses very high hardness and excellent corrosion resistance in 3.5% NaCl solution, demonstrating by nearly ten times of hardness higher and two orders of magnitude of corrosion rate lower than the magnesium substrate. Similarly to 316L stainless steel coatings, the current Fe-based amorphous coating with a very large passive region, shows much more positive of corrosion potential and much less corrosion current density than that of sprayed Al alloy coating and ceramic coatings on magnesium alloys previously reported. The outstanding feature of the protective magnesium alloy with amorphous coating can be attributed to its unique disorder structure and uniform chemical composition, which allows a very dense passivation film formed and uniform corrosion occurred. Our findings demonstrate that Fe-based amorphous coating is a promising candidate for protecting magnesium alloys with desirable corrosion resistance for structural/functional applications.