Nanostructured YSZ is expected to exhibit a high strain tolerability due to its low Young’s modulus and consequently high durability. In this study, a porous YSZ as the thermal barrier coating was deposited by plasma spraying using an agglomerated nanostructured YSZ powder on a Ni-based superalloy Inconel 738 substrate with a cold-sprayed nanostructured NiCrAlY as the bond coat. The heat treatment in Ar atmosphere was applied to the cold-sprayed bond coat before deposition of YSZ. The isothermal oxidation and thermal cycling tests were applied to examine failure modes of plasma-sprayed nanostructured YSZ. The results showed that YSZ coating was deposited by partially melted YSZ particles. The nonmelted fraction of spray particles retains the porous nanostructure of the starting powder into the deposit. YSZ coating exhibits a bimodal microstructure consisting of nanosized particles retained from the powder and micro-columnar grains formed through the solidification of the melted fraction in spray particles. The oxidation of the bond coat occurs during the heat treatment in Ar atmosphere. The uniform oxide at the interface between the bond coat and YSZ can be formed during isothermal test. The cracks were observed at the interface between TGO/BC or TGO/YSZ after thermal cyclic test. However, the failure of TBCs mainly occurred through spalling of YSZ within YSZ coating. The failure characteristics of plasma-sprayed nanostructured YSZ are discussed based on the coating microstructure and formation of TGO on the bond coat surface.