Certain Vibrio cholerae strains produce cholix, a potent protein toxin that has diphthamide-specific ADP-ribosyltransferase activity against eukaryotic elongation factor 2. Here we present a 1.8 Å crystal structure of cholix in complex with its natural substrate, nicotinamide adenine dinucleotide (NAD(+)). We also substituted hallmark catalytic residues by site-directed mutagenesis and analyzed both NAD(+) binding and ADP-ribosyltransferase activity using a fluorescence-based assay. These data are the basis for a new kinetic model of cholix toxin activity. Further, the new structural data serve as a reference for continuing inhibitor development for this toxin class.