Gadolinium zirconate (Gd2Zr2O7, GZ) as one of the promising thermal barrier coating materials for high-temperature application in gas turbine was toughened by nanostructured 3mol% yttria partially-stabilized zirconia (3YSZ) incorporation. The fracture toughness of the composite of 90mol%GZ-10mol% 3YSZ (GZ-YSZ) was increased by about 60% relative to the monolithic GZ. Both the GZ and GZ-YSZ composite coatings were deposited by atmospheric plasma spraying on Ni-base superalloys and then thermal-shock tested under the same conditions. The thermal-shock resistance of GZ-YSZ composite coating was improved significantly, which is believed to be mainly attributed to the enhancement of fracture toughness by the addition of nanostructured 3YSZ. In addition, the failure mechanisms of the thermal-shock tested GZ and GZ-YSZ composite coatings were also discussed.