Alumina-zirconia nano-composite coating were fabricated by plasma spraying using agglomerated feedstock from alumina and yttria partially stabilized zirconia fine powders of about 100 nm in diameter. The coating was very dense and showed the striped contrast in the splats. XRD analysis and TEM observation revealed that the splats contained gamma-alumina and tetragonal-zirconia crystals, which sizes were under 10 nm. The striped contrast in the splats corresponded to the inhomogeneous distributions of these crystals. To investigate the mechanical properties of this nano-composite coating, micro-hardness and fracture toughness were measured. The critical strain energy release rate of nano-composite coating was 106.4 J/m2, which was two times larger than YSZ coating.