A new type of composite coating (321—Al coating) was prepared by using the 321 austenitic stainless steel wire feed stock as the anode and aluminum wire as the cathode in arc spraying process. In order to compare with the new composite coating, the traditional 321 coating with twin 321 stainless steel wires was fabricated. The microstructure and wear resistance of the coatings were characterized by means of scanning electron microscopy (SEM), X-ray diffraction (XRD), energy dispersion spectroscope (EDS) and MM-200 ring-block type sliding wear tester. Results showed that, except for the aluminum phase addition in the 321—Al coating, no other extra phases produce in comparing with the 321 coating. However, due to the additional aluminum, the 321—Al coating performs quite different microstructure characteristics and tribological behavior. The oxygen content and microhardness of the 321—Al coating are lower than that of the 321 coating, but wear losses are pretty much under the oil lubricated sliding condition. The effect of the microstructure on the wear behavior of the 321—Al coating was also discussed, which is mainly relevant to the characteristic of “ductile aluminum and hard stainless steel composite phases inter-depositing”.