The tripartite cytolethal distending toxin (CDT) induces cell cycle arrest and apoptosis in eukaryotic cells. The subunits CdtA and CdtC associate with the nuclease CdtB to form a holotoxin that translocates CdtB into the host cell, where it acts as a genotoxin by creating DNA lesions. Here we show that the crystal structure of the holotoxin from Haemophilus ducreyi reveals that CDT consists of an enzyme of the DNase-I family, bound to two ricin-like lectin domains. CdtA, CdtB and CdtC form a ternary complex with three interdependent molecular interfaces, characterized by globular, as well as extensive non-globular, interactions. The lectin subunits form a deeply grooved, highly aromatic surface that we show to be critical for toxicity. The holotoxin possesses a steric block of the CdtB active site by means of a non-globular extension of the CdtC subunit, and we identify putative DNA binding residues in CdtB that are essential for toxin activity.