Despite a sizeable body of research, the efficacy of therapeutic cancer vaccines remains limited when applied as sole agents. By using a prime:boost approach involving two viral cancer vaccines, we were able to generate large tumor-specific CD8+ T-cell responses in a murine model of disseminated pulmonary melanoma. Significant increases in the number and quality of circulating effector T-cells were documented when low-dose cyclophosphamide (CTX) was administered pre-vaccination to tumor-bearing but not tumor-free hosts. Interestingly, tumor-bearing mice receiving CTX and co-primed with a melanoma differentiation antigen together with an irrelevant control antigen exhibited significantly enhanced immunity against the tumor, but not the control antigen, in secondary lymphoid organs. This result highlighted an increased cancer-specific reactivity of vaccine-induced T-cell responses following CTX preconditioning. Additionally, an acute reduction of the frequency of peripheral regulatory T-cells (Tregs) was noticeable, particularly in the proliferating, presumably tumour-reactive, subset. Enhanced infiltration of lungs with multifunctional T-cells resulted in overt reduction in metastatic burden in mice pretreated with CTX. Despite doubling the median survival in comparison to untreated controls, most vaccinated mice ultimately succumbed to cancer progression. However, preconditioning of the virus-based vaccination with CTX resulted in a remarkable improvement of the therapeutic activity leading to complete remission in the majority of the animals. Collectively, these data reveal how CTX can potentiate specific cellular immunity in an antigen-restricted manner that is only observed in vaccinated tumor-bearing hosts while depleting replicating Tregs. A single low dose of CTX enhances antitumor immunity and the efficacy of this potent prime:boost platform by modulating the kinetics of the vaccine-specific responses. Clinical assessment of CTX combined with next-generation cancer vaccines is indicated.