Using Caenorhabditis elegans as an infection host model for Vibrio cholerae predator interactions, we discovered a bacterial cytotoxin, MakA, whose function as a virulence factor relies on secretion via the flagellum channel in a proton motive force-dependent manner. The MakA protein is expressed from the polycistronic makDCBA (motility-associated killing factor) operon. Bacteria expressing makDCBA induced dramatic changes in intestinal morphology leading to a defecation defect, starvation and death in C. elegans. The Mak proteins also promoted V. cholerae colonization of the zebrafish gut causing lethal infection. A structural model of purified MakA at 1.9 Å resolution indicated similarities to members of a superfamily of bacterial toxins with unknown biological roles. Our findings reveal an unrecognized role for V. cholerae flagella in cytotoxin export that may contribute both to environmental spread of the bacteria by promoting survival and proliferation in encounters with predators, and to pathophysiological effects during infections.