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.