A new composite ceramic material based on corundum and reinforced with multilayer carbon nanotubes (CNTs) obtained by catalytic pyrolysis has been developed. Regimes for vacuum calcination and preliminary treatment of the initial mix have been determined; the compositions of the ceramic matrix, the concentration of the CNTs, and other technological parameters have been optimized. A uniform distribution of CNTs over the entire volume of the ceramic matrix has been achieved. As a result, a composite material with a reticular-framework structure of the CNT distribution showing a 1.5-2-fold increase of the cracking resistance has been obtained.