The dissemination of tumor cells with ensuing metastasis is responsible for most cancer-related deaths. Cancer vaccines may, by inducing tumor-specific effector T cells, offer a strategy to eliminate metastasizing tumor cells. However, several obstacles remain in the development of effective cancer vaccines, including the identification of adjuvants that enhance the evolvement and efficacy of tumor-specific T cells. Cholera toxin-based adjuvants have shown efficacy in vaccines for infectious diseases, but their role in cancer vaccine therapies remains to be elucidated. Here, we explored the potential of cholera toxin A1 (CTA1)-based adjuvants to boost anti-tumor T cell responses and protect against metastasis. We report that an adjuvant where CTA1 was fused to a dimer from Staphylococcus aureus protein A (DD) enhanced immune responses against the tumor-associated antigens TRP2 and Twist1 in mice, providing protection against B16F1 melanoma and 4T1 breast cancer metastasis, respectively. Both mucosal (intranasal) and systemic (intraperitoneal) vaccine administration provided effective protection against intravenously injected tumor cells, with intranasal administration leading to superior induction of CD4+ T cells at metastatic sites. When comparing antigens admixed with CTA1-DD to those fused with a CTA1-based adjuvant, the fusion construct elicited the strongest immunogenicity. Nevertheless, by administrating a 20-fold higher antigen dose also the admix formulation provided efficient protection against metastasis.