Al-Ni-Y-Co and Al-Ni-Mm-Fe amorphous and nanocrystalline composite coatings were prepared on the surface of AZ91 magnesium alloy by automatic high velocity arc spraying system. The microstructures of the composite coatings were analyzed by scanning electron microscope (SEM) and X-ray diffraction (XRD). The results show that the composite coatings compose of amorphous phases and crystalline phases. The composite coatings have a compact structure with low porosity. The Vickers microhardness HV of Al-Ni-Y-Co and Al-Ni-Mm-Fe coatings is 3117.6 MPa and 3407.2 MPa, respectively, which is about four times higher than that of the traditional Al-RE coatings and five times higher than that of the AZ91 magnesium alloy. The electrochemistry experimental results show that the corrosion resistances of the Al-Ni-Y-Co and Al-Ni-Mm-Fe amorphous and nanocrystalline composite coatings are superior to those of the traditional Al-RE coatings and AZ91 magnesium alloy.