High velocity arc spraying (HVAS) process was used to deposit Al-Ni-Y-Co and Al-Ni-Mm-Fe amorphous/nanocrystalline composite coatings onto AZ91 Mg alloy substrate. Their microstructure was characterized by using X-ray diffraction (XRD), scanning electron microscopy (SEM) and transmission electron microscopy (TEM). The coatings are both about 500 μm in thickness with fully dense and low porosity. The microstructure of the coatings is classified into two regions, namely, a full amorphous phase region and homogeneous dispersion of fcc-Al and some intermetallic nanoscale particles in a residual amorphous matrix region. Vickers micro hardness of the coatings was also measured. The average Vickers micro hardness of Al-Ni-Y-Co and Al-Ni-Mm-Fe coating is about 311 HV and 340 HV, respectively.