A coating about 3-mm thick of the amorphous alloy, Zr65Al7.5Ni10Cu17.5 was fabricated on magnesium substrates using the technique of laser multi-layer cladding protected under an atmosphere of argon gas. The coating exhibited a graded microstructure, which could be generally categorized into three classes: an amorphous phase, an amorphous–nanocrystalline composite, and one which is predominantly crystalline. Formation of the latter two was due to the reheating effect of the laser cladding process. With regard to properties, the microhardness and the wear resistance of the composite material were both higher than that of the monolithic amorphous material; both materials showed excellent corrosion resistance in a 3.5% NaCl solution.