Cancer vaccines can induce robust activation of tumor-specific CD8(+) T cells that can destroy tumors. Understanding the mechanism by which cancer vaccines work is essential in designing next-generation vaccines with more potent therapeutic activity. We recently reported that short peptides emulsified in poorly biodegradable, Incomplete Freund's Adjuvant (IFA) primed CD8(+) T cells that did not localize to the tumor site but accumulated at the persisting, antigen-rich vaccination site. The vaccination site eventually became a T cell graveyard where T cells responded to chronically released gp100 peptide by releasing cytokines, including interferon-γ (IFN-γ), which in turn upregulated Fas ligand (FasL) on host cells, causing apoptosis of Fas(+) T cells. T cells that escaped apoptosis rapidly became exhausted, memory formation was poor, and therapeutic impact was minimal. Replacing the non-biodegradable IFA-based formulation with water-based, short-lived formulation in the presence of immunostimulatory molecules allowed T cells to traffic to tumors, causing their regression. In this review, we discuss recent advances in immunotherapeutic approaches that could enhance vaccine-primed immune cells fitness and render the tumor microenvironment more accessible for immune cell infiltration.