The conventional and nanostructured Al2O3-13TiO2 composite ceramic coatings(ω/%, similarly hereinafter) were fabricated by plasma spraying on TiAl alloy surface with conventional and nanostructured agglomerated powders as starting materials. The morphology, microstructure and phase composition of the powder and the coating were investigated by means of scanning electron microscopy (SEM) and X-ray diffractometry (XRD). Meanwhile, the formation mechanism of the coating microstructure was discussed. The results show that the conventional composite ceramic coating presents typical plasma-spraying lamellar accumulation structure. However, the nanostructured ceramic coating consists of not only fully melted regions but also partially melted regions, and the fully melted region has a lamellar-like structure as conventional coating. According to the different microstructure, the partially melted regions can be divided into liquid-phase sintered regions (three-dimensional net or skeleton-like structure: submicron Al2O3 particles distributed in the TiO2 matrix) and solid-phase sintered regions (residual nanoparticles have grown to some extent but still remained nano-scale). The different partially melted regions come from the difference of the melting point between A12O3 and TiO2. The main phase, in both the conventional and nanostructured coating, is the metastable phase of γ-Al2O3 due to the rapid solidification during the deposition of plasma spraying.