Particle Mediated Epidermal Delivery (PMED) is a potent genetic vaccination method. However, a recent report found PMED only poorly and infrequently triggered antigen-specific cytotoxic T-cells in cancer patients. Here, we show that injection of the chemotherapeutic drug Gemcitabine in mice results in improvement of the efficacy of subsequent PMED vaccination against NY-ESO-1. We found in mice and in cancer patients that administration of Gemcitabine induces a transient reduction in the percentage of regulatory T-cells among CD4-positive cells. The higher relative sensitivity of regulatory T-cells compared with other CD4-positive T-cells towards cytostatic drugs can be linked to the higher frequency of proliferating cells in the regulatory compartment compared with the non-regulatory CD4-compartment in healthy people and cancer patients. Thus, by affecting regulatory T-cells more than other lymphocyte subsets, chemotherapeutic agents can create a transient hyper-immunoreactive window. Such a window would provide an ideal timepoint to administer a vaccine expected to induce a therapeutically relevant anti-cancer cytotoxic T-cell response.