A main goal of cancer immunology research is the formation of antigen-specific memory T cell immunity capable of activation upon tumor re-encounter. The requirements necessary to overcome the inhibitory signals present in the tumor microenvironment and form such memory T cell responses are unknown. In contrast to previous studies targeting tumors expressing highly-immunogenic “model antigens,” we demonstrate that alleviating tumor-induced suppression along with vaccination against authentic antigens during the perioperative period provides long-lasting protection against a highly-suppressive and poorly-immunogenic melanoma. Here, we employed DNA vaccination with an immunologically optimized mouse melanoma-shared antigen, Trp1ee/ng, combined with systemic TGF-β blockade during the perioperative period of primary tumor resection, to confer protection against B16 melanoma, and against JBRH, an independently-derived melanoma unrelated to B16. Importantly, we demonstrate that correlative to memory responses, perioperative immunotherapy increases the formation of tumor-infiltrating and tumor-reactive CD8+ T cells expressing low levels of the transcription factor T-bet, defined as memory precursor effector cells (MPECs). We show that conditions for an “immunologically-fertile environment” are met when TGF-β blockade and vaccination are applied during the perioperative period of primary tumor resection. These findings address limitations of current CD8+ T cell immunotherapies against cancer by generating effective CD8+ T cell memory recall responses.