Defining correlates of T cell mediated protection is important in order to accelerate the development of efficient T cell based vaccines conferring long-term immunity. Extensive studies have provided important insight regarding the characteristics and functional properties of the effector and memory CD8 T cells induced by viral vector based vaccines. However, long-term protection has been difficult to achieve with T cell inducing vaccines, and the determinants underlying this loss in protection over time are still not fully defined. In this study we analyzed different parameters of the CD8 T cell response as a function of time after vaccination with a human serotype 5 adenovector expressing the glycoprotein (GP) of LCMV tethered to the MHC class II-associated invariant chain. Using this vector we have previously found that CD8 T cells mediate protection from challenge with GP-expressing Listeria monocytogenes at 60 days post vaccination, but only little protection after further 60 days, and we now confirm this observation. A comparison of vaccine-primed CD8 T cells early and late after vaccination revealed a minor decline in the overall numbers of antigen specific memory CD8 T cells during this interval. More importantly, we also observed phenotypic changes over time with a distinct decline in the frequency and number of KLRG1+ CD8 T cells, and, notably, adoptive transfer studies confirmed that memory CD8 T cells expressing KLRG1 are central to protection from systemic L. monocytogenes infection. Together these findings imply that multiple factors including changes in memory T cell numbers and phenotypic composition over time influence the longevity of CD8 T-cell mediated protection.