Most studies on E1-deleted adenovirus (Ad) vectors as vaccine carriers for antigens of HIV-1 have focused on induction of central immune responses, although stimulation of mucosal immunity at the genital tract (GT), the primary port of entry of HIV-1, would also be highly desirable. In this study, different immunization protocols using chimpanzee-derived adenoviral (AdC) vectors expressing Gag of HIV-1 clade B given in heterologous prime-boost regimens were tested for induction of systemic and genital immune responses. Although i.n. immunization stimulated CD8(+) T-cell responses that could be detected in the GT, this route induced only marginal cellular responses in systemic tissues and furthermore numbers of Gag-specific CD8(+) T cells contracted sharply within a few weeks. On the contrary, i.m. immunization induced higher and more sustained frequencies of vaccine-induced cells which could be detected in the GT as well as systemic compartments. Antigen-specific CD8(+) T cells could be detected 1 year after immunization in all compartments analyzed. Genital memory cells secreted IFN-γ, expressed high levels of CD103 and their phenotypes were consistent with a state of activation. Taken together, the results presented here show that i.m. vaccination with chimpanzee-derived (simian) adenovirus vectors is a suitable strategy to induce a long-lived genital CD8(+) T-cell response.