Production of the pro-inflammatory cytokine IL-12 by innate phagocytes drives the differentiation of IFN-gamma-producing effector T cells during Toxoplasma gondii infection. However, the role of IL-12 in the regulation of memory CD8+ T cell differentiation and function during murine toxoplasmosis is unclear. To track memory CTL development, we identified a novel H-2K(b)-restricted CTL population specific for the Toxoplasma antigen tgd057. Tgd057-specific CTLs were induced by both vaccination and natural peroral infection, and were representative of the polyclonal CTL population. Tgd057-specific primary effector cells required IL-12 for the differentiation of KLRG1+ effector subpopulations and IFN-gamma production in response to restimulation with parasite-infected cells, but not to restimulation with cognate peptide. The effect of IL-12 deficiency during the primary response was profoundly imprinted on memory CTLs, which continued to show defects in cell numbers, KLRG1+ effector memory subpopulation differentiation, and IFN-gamma recall responses. Importantly, isolated CD62L(hi) KLRG1- CD8+ T cells differentiated in the absence of IL-12 were enhanced in their ability to generate IFN-gamma-producing secondary tgd057-specific effector cells. Our data, for the first time, demonstrate the negative impact of IL-12 signaling on the quality of the central memory CTL compartment. Thus, despite the beneficial role of IL-12 in promoting effector differentiation, excessive exposure to IL-12 during CTL priming may limit the development of long-term protective immunity through the decreased fitness of central memory CTL responses.