Rechargeable magnesium batteries (RMBs) have attracted much attention because of their high theoretical volumetric capacity and high safety. However, the uneven deposition behavior, harmful corrosion reaction and poor stability of magnesium metal anodes have hindered the practical application of RMBs. Herein, we propose a facile alloy electrodeposition method to construct an artificial layer on an Mg anode. Experimental results show that the polarization of the symmetric magnesium alloy-based (Mg-Sn@Mg and Mg-Bi@Mg) cells is significantly reduced (∼0.05 V) at a current density of 0.1 mA cm-2. The symmetric cells using the prepared Mg alloy anodes exhibited lower voltage hysteresis and ultra-stable cycling performance at a higher density of 1.0 mA cm-2 over 700 h. The in situ optical microscopy study clearly demonstrated that the Mg dendrite formation was successfully retarded by the designed Mg-Sn and Mg-Bi alloy artificial protective layer on Mg anodes. The superiority of Mg-Sn@Mg and Mg-Bi@Mg was further confirmed in full cells using Mo6S8 as the cathode. Compared with the Mo6S8//Mg full cell, the Mo6S8//Mg-Sn@Mg and Mo6S8//Mg-Bi@Mg full cells maintained an ultra-stable electrochemical performance even after 5000 cycles. This proof-of-concept provides a novel scope for the artificial coating layers on Mg anodes prepared by alloy electrodeposition and can be extended to other alloy anodes (i.e. Mg-Cu@Mg and so on). This work provides an avenue for the design of practical and high-performance RMBs and beyond.