MARTX toxins modulate the virulence of a number of Gram-negative Vibrio species. This family of toxins is defined by the presence of a cysteine protease domain (CPD), which proteolytically activates the Vibrio cholerae MARTX toxin. Although recent structural studies of the CPD have uncovered a new allosteric activation mechanism, the mechanism of CPD substrate recognition or toxin processing is unknown. Here we show that interdomain cleavage of MARTXVc enhances effector domain function. We also identify the first small-molecule inhibitors of this protease domain and present the 2.35-A structure of the CPD bound to one of these inhibitors. This structure, coupled with biochemical and mutational studies of the toxin, reveals the molecular basis of CPD substrate specificity and underscores the evolutionary relationship between the CPD and the clan CD caspase proteases. These studies are likely to prove valuable for devising new antitoxin strategies for a number of bacterial pathogens.