The role of CD4+ T cells in the generation of therapeutic primary and memory immune responses in cancer diverse immunotherapy settings remains ambiguous. We herein investigated this issue using two vaccine formulations containing a novel costimulatory molecule, SA-4-1BBL, as adjuvant and HPV E7 or survivin (SVN) as tumor associated antigens (TAAs) in two mouse transplantable tumor models; the TC-1 cervical cancer expressing xenogeneic HPV E7 and 3LL lung carcinoma overexpressing autologous SVN. Single vaccination with optimized SA-4-1BBL/TAA formulations resulted in the eradication of 6-day established TC-1 and 3LL tumors in >70% of mice in both models. The in vivo depletion of CD4+ T cells one day before tumor challenge resulted in compromised vaccine efficacy in both TC-1 (25%) and 3LL (12.5%) tumor models. In marked contrast, depletion of CD4+ T cells 5 days post-tumor challenge and one day prior to vaccination did not significantly alter the therapeutic efficacy of these vaccines. However, long-term immunological memory was compromised in the 3LL, but not in TC-1 model as a significant number (85.7%) of tumor free-mice succumbed to tumor growth when rechallenged with 3LL cells 60 days after the initial tumor inoculation. Collectively, these results demonstrate the indispensable role CD4+ T cells play in the generation of therapeutic primary immune responses elicited by SA-4-1BBL/TAA-based vaccines irrespective of the nature of TAAs and establish the importance of CD4+ T cells for long-term immune memory against 3LL tumor expressing self-antigen SVN, but not TC-1 expressing xenogeneic viral antigen E7.