Al2O3-TiO2-ZrO2-CeO2 coatings formed via a plasma spray approach. The optimal spray parameters of plasma sprayed nano-structured coating were determined by orthogonal experimental design, based on porosity, bond strength of the coatings and the partly melted(PM) zone percentage. Microstructure of the plasma sprayed nanostructured Al2O3-TiO2-ZrO2-CeO2 coating sprayed on the optimal spray parameters was analyzed. Wear map was established by wear experiments. The results show, nanostructured coating contains fully melted (FM) zone and PM zone, the increasing of the critical plasma spray parameter (CPSP) promote the decreasing of the PM zone percentage and the increasing of the bond strength of the coatings. The composition phases of the powder reacted to each other during the plasma spraying process. FM and PM zone resulted from fully melted droplets and partly melted particles respectively. Nanosized crystals and amorphous particles exist in the PM zone, liquid phase sintering is taken place in the PM zone. The main wear mechanism of plasma spraying coatings are plastic deformation and microplow, microfracture and grain spalling, fracture and delamination at different normal load and sliding speed in dry friction.