Most infections are caused by pathogens that access the body at mucosal sites. Hence, development of mucosal vaccines to prevent local infection or invasion of pathogens appears highly warranted, especially since only mucosal immunization will stimulate strong local IgA responses and tissue resident memory CD4 and CD8 T cells. The most significant obstacle to developing such vaccines is the lack of approved adjuvants that can effectively and safely enhance relevant mucosal and systemic immune responses. The most potent mucosal adjuvants known today are the adenosine diphosphate (ADP)-ribosylating bacterial enterotoxins cholera toxin (CT) and Escherichia coli heat-labile toxins (LTs). Unfortunately, these molecules are also very toxic, which precludes their clinical use. However, much effort has been devoted to developing derivatives of these enterotoxins with low or no toxicity and retained adjuvant activity. Although it is fair to say that we know more about how these toxins affect the immune system than ever before, we still lack a detailed understanding of how and why these toxins are effective adjuvants. In the present review, we provide a state-of-the-art overview of the mechanism of action of the holotoxins and the strategies used for improving the toxin-based adjuvants.