Adenoviral vectors have shown a great potential for vaccine development due to their inherent ability to induce potent and protective CD8 T-cell responses. However, a critical issue regarding the use of these vectors is the existence of inhibitory immunity against the most commonly used Ad5 vector in a large part of the human population. We have recently developed an improved adenoviral vaccine vector system in which the vector expresses the transgene tethered to the MHC class II associated invariant chain (Ii). To further evaluate the potential of this system, the concept of pre-existing inhibitory immunity to adenoviral vectors was revisited to investigate whether the inhibition previously seen with the Ad5 vector also applied to the optimized vector system. We found this to be the case, and antibodies dominated as the mechanism underlying inhibitory vector immunity. However, presence of CD8 T cells directed against epitopes in the adenoviral vector seemed to correlate with repression of the induced response in re-vaccinated B-cell deficient mice. More importantly, despite a repressed primary effector CD8 T-cell response in Ad5-immune animals subjected to vaccination, memory T cells were generated that provided the foundation for an efficient recall response and protection upon subsequent viral challenge. Furthermore, the transgene specific response could be efficiently boosted by homologous re-immunization. Taken together, these studies indicate that adenoviral vectors can be used to induce efficient CD8 T-cell memory even in individuals with pre-existing vector immunity.