Multi-walled carbon nanotube (MWCNT)/nanostructured zirconia composites with a homogenous distribution of different MWCNT quantities (ranging within 0.5-5 wt.%) were developed. By using Spark Plasma Sintering we succeeded in preserving the MWCNTs firmly attached to zirconia grains and in obtaining fully dense materials. Moreover, MWCNTs reduce grain growth and keep a nanosize structure. A significant improvement in room temperature fracture toughness and shear modulus as well as an enhanced creep performance at high temperature is reported for the first time in this type of materials. To support these interesting mechanical properties, high-resolution electron microscopy and mechanical loss measurements have been carried out. Toughening and creep hindering mechanisms are proposed. Moreover, an enhancement of the electrical conductivity up to 10 orders of magnitude is obtained with respect to the pure ceramics. (C) 2011 Elsevier Ltd. All rights reserved.