Archaeosomes constitute archaeal lipid vesicle vaccine adjuvants that evoke a strong CD8+ T cell response to antigenic cargo. Therapeutic treatment of murine B16-ovalbumin (B16-OVA) melanoma with archaeosome-OVA eliminates small subcutaneous solid tumors; however, they eventually resurge despite an increased frequency of circulating and tumor infiltrating OVA-CD8+ T cells. Herein, a number of different approaches were evaluated to improve responses, including dose number, interval, and the combination of vaccine with checkpoint inhibitors. Firstly, we found that tumor protection could not be enhanced by repetitive and/or delayed boosting to maximize the CD8+ T cell number and/or phenotype. The in vivo cytotoxicity of vaccine-induced OVA-CD8+ T cells was impaired in tumor-bearing mice. Additionally, tumor-infiltrating OVA-CD8+ T cells had an increased expression of programmed cell death protein-1 (PD-1) compared to other organ compartments, suggesting impaired function. Combination therapy of tumor-bearing mice with the vaccine archaeosome-OVA, and α-CTLA-4 administered concurrently as well as α-PD-1 and an α-PD-L1 antibody administered starting 9 days after tumor challenge given on a Q3Dx4 schedule (days 9, 12, 15 and 18), significantly enhanced survival. Following multi-combination therapy ~70% of mice had rapid tumor recession, with no detectable tumor mass after >80 days in comparison to a median survival of 17–22 days for untreated or experimental groups receiving single therapies. Overall, archaeosomes offer a powerful platform for delivering cancer antigens when used in combination with checkpoint inhibitor immunotherapies.