Heterologous prime-boost vaccination using plasmid DNA followed by replication-defective adenovirus vector generates a large number of specific CD8⁺ T effector memory (TEM) cells that provide long-term immunity against a variety of pathogens. In the present study, we initially characterized the frequency, phenotype, and function of these T cells in vaccinated mice that were subjected to infectious challenge with the human protozoan parasite Trypanosoma cruzi. We observed that the frequency of the specific CD8⁺ T cells in the spleens of the vaccinated mice increased after challenge. Specific TEM cells differentiated into cells with a KLRG1(High) CD27(Low) CD43(Low) CD183(Low)T-bet(High) Eomes(Low) phenotype and capable to produce simultaneously the antiparasitic mediators IFNγ and TNF. Using the gzmBCreERT2/ROSA26EYFP transgenic mouse line, in which the cells that express Granzyme B after immunization, are indelibly labeled with enhanced yellow fluorescent protein, we confirmed that CD8⁺ T cells present after challenge were indeed TEM cells that had been induced by vaccination. Subsequently, we observed that the in vivo increase in the frequency of the specific CD8⁺ T cells was not because of an anamnestic immune response. Most importantly, after challenge, the increase in the frequency of specific cells and the protective immunity they mediate were insensitive to treatment with the cytostatic toxic agent hydroxyurea. We have previously described that the administration of the drug FTY720, which reduces lymphocyte recirculation, severely impairs protective immunity, and our evidence supports the model that when large amounts of antigen-experienced CD8⁺ TEM cells are present after heterologous prime-boost vaccination, differentiation, and recirculation, rather than proliferation, are key for the resultant protective immunity.