The application of magnesium (Mg) inevitably involves dissimilar welding with steel. A novel solid state spot welding method, refill friction stir spot welding (refill FSSW), was utilized to weld AZ31 Mg alloy to galvanized DP600 steel. Although Mg/Fe is an immiscible alloy system, defect-free welds with high strength were successfully obtained in a wide parameter window. The results of microstructure, interfacial reactions, and mechanical properties are reported to reveal the underlying joining mechanism. Due to the melting of Zn coating and subsequent Mg-Zn reactions, Mg-Zn eutectic and intermetallic compounds were detected within welds. Heterogeneous interfacial reactions occur along Mg/steel interface, and the relationship between interfacial structure and fracture behavior was investigated. The joining mechanism is associated with Zn coating and Fe-Al layer: 1) the presence of Zn coating is beneficial for achieving high-quality welding between Mg and steel, it protects the interface from oxidation and contributes to brazing of the weld; 2) the Al present in Mg alloy reacts with Fe, resulting in the growth of Fe-Al layer, which contributes to the diffusion bonding in the interface. The overall results clearly show that refill FSSW is a competitive welding method for joining Mg and galvanized steel.