Aluminum (Al) coating was thermally sprayed on the surface of AZ80 magnesium (Mg) alloy. The Al-coating was deformed at 400°C with different deformation degrees of 15%, 30%, 45%, 60% and 80%. The corrosion properties of the AZ80 Mg alloys coated with Al-coatings were studied by potentiodynamic and galvanic tests in 3.5% NaCl solution; the adhesion strengths between Al-coatings and AZ80 substrate were also measured simultaneously by tensile test. The results showed that, Al-coating could decrease the corrosion rate of AZ80 Mg alloys, and the corrosion rate was related not only with the density of Al-coating but also with the adhesion strength of Al-coating. Before the formation of dense Al-coating, the corrosion rate of Al-coated AZ80 Mg alloys decreased with the increasing of bonding strength of Al-coating; after the formation of dense Al-coating, the corrosion rate of Al-coated AZ80 Mg was mainly determined by the structure of Al-coating. It was also revealed that with the increasing of deformation degree, the corrosion rate of the Al-coated AZ80 Mg alloys first decreased then increased, while the adhesion strength increased gradually. The corrosion rate of AZ80 Mg alloy coated with 60% deformed Al-coating was the lowest, which was only 19% of that of the AZ80 substrate.