The excellent mechanical properties of carbon nanotubes (CNTS) are driving research into the creation of new strong, tough nanocomposite systems. Here, the first evidence of toughening mechanisms operating in carbon-nanotube-reinforced ceramic composites is presented. A highly ordered array of parallel multiwall CNTs in an alumina matrix was fabricated. Nanoindentation introduced controlled cracks and the damage was examined by scanning electron microscopy. These nanocomposites exhibit the three hallmarks of toughening found in micron-scale fiber composites: crack deflection at the CNT/matrix interface; crack bridging by CNTs; and CNT pullout on the fracture surfaces. Interface debonding and sliding can thus occur in materials with microstructures approaching the atomic scale. Furthermore, for certain geometries a new mechanism of nanotube collapse in "shear bands" occurs, rather than crack formation, suggesting that these materials can have multiaxial damage tolerance. The quantitative indentation data and computational models are used to determine the multiwall CNT axial Young's modulus as 200-570 GPa, depending on the nanotube geometry and quality. Three-dimensional FEM analysis indicates that matrix residual stresses on the order of 300 MPa are sustained in these materials without spontaneous cracking, suggesting that residual stress can be used to engineer enhanced performance. These nanoscale ceramic composites thus have potential for toughening and damage tolerance at submicron scales, and so are excellent candidates for wear-resistant coatings. Published by Elsevier Ltd on behalf of Acta Materialia Inc.