Mutant cholera holotoxins comprising a cholera toxin subunit A having single amino acid substitutions in the amino acid positions 16 or 72 or a double amino acid substitution in the amino acid positions 16 and 68 or 68 and 72 have reduced toxicity compared to the wild-type cholera holotoxin. The mutant cholera holotoxins are useful as adjuvants in immunogenic compositions to enhance the immune response in a vertebrate host to a selected antigen from a pathogenic bacterium, virus, fungus, or parasite, a cancer cell, a tumor cell, an allergen, or a self-molecule.