In the present work, ultra-fine Al2O3/ZrO2-MgO-CeO2 powders were used as the starting materials to produce Al2O3-ZrO2 composite coatings on 45# carbon steel by flame spray. The ultra-fine Al2O3/ZrO2-MgO-CeO2 powders were prepared via the co-precipitation method accompanied a crushing sintering process. The microstructure, the phase compositions and the bond strength of the crushed sintered powders and the corresponding composite coatings were investigated by scanning electron microscopy (SEM), X-ray diffraction (XRD) and a tensile bond strength tests respectively. It was found that the phase composition, the surface topography and the coating adhesion were different from the difference kinds of coatings. Results indicated that the phase composition of the flame sprayed ceramic coatings consisted of tetragonal-ZrO2, cubic-ZrO2, ZTA (zirconia toughened alumina) and γ-Al2O3, with a small amount of α-Al2O3, and that bond strength values attained 45.1 MPa for 42.6wt.% Al2O3/57.4wt.% Mg0.13Ce0.1Zr0.77O1.87 coating.