Cholera toxin and its close relative, Escherichia coli heat-labile enterotoxin, are potent immunogens and mucosal adjuvants. The recent findings that their B subunits can promote tolerance highlights the complexity of their interactions with the immune system. Here, Neil Williams and colleagues review the mechanisms by which these molecules modulate leukocyte populations and seek to explain the paradox.