HIV-1-specific CD4+ and CD8+ T lymphocytes are important for HIV-1 replication control. F4/AS01 consists of F4 recombinant fusion protein (containing clade B Gag/p24, Pol/RT, Nef and Gag/p17) formulated in AS01 Adjuvant System, and was shown to induce F4-specific polyfunctional CD4+ T-cell responses in humans. While replication-incompetent recombinant HIV-1/SIV antigen-expressing human adenoviral vectors can elicit high-frequency antigen-specific CD8+ T-cell responses, their use is hampered by widespread pre-existing immunity to human serotypes. Non-human adenovirus serotypes associated with lower prevalence may offer an alternative strategy. We evaluated the immunogenicity of AdC7-GRN ('A'), a recombinant chimpanzee adenovirus type 7 vector expressing clade B Gag, RT and Nef, and F4/AS01 ('P'), when delivered intramuscularly in homologous (PP or AA) and heterologous (AAPP or PPAA) prime-boost regimens, in macaques and mice. Vaccine-induced HIV-1-antigen-specific T cells in peripheral blood (macaques), liver, spleen, and intestinal and genital mucosa (mice) were characterized by intracellular cytokine staining. Vaccine-specific IgG antibodies (macaques) were detected using ELISA. In macaques, only the heterologous prime-boost regimens induced polyfunctional, persistent and balanced CD4+ and CD8+ T-cell responses specific to each HIV-1 vaccine antigen. AdC7-GRN priming increased the polyfunctionality of F4/AS01-induced CD4+ T cells. Approximately 50% of AdC7-GRN-induced memory CD8+ T cells exhibited an effector-memory phenotype. HIV-1-specific antibodies were detected with each regimen. In mice, antigen-specific CD4+ and CD8+ T-cell responses were detected in the mucosal and systemic anatomical compartments assessed. When administered in heterologous prime-boost regimens, AdC7-GRN and F4/AS01 candidate vaccines acted complementarily in inducing potent and persistent peripheral blood HIV-1-specific CD4+ and CD8+ T-cell responses and antibodies in macaques. Besides, adenoviral vector priming modulated the cytokine-expression profile of the protein-induced CD4+ T cells. Each regimen induced HIV-1-specific T-cell responses in systemic/local tissues in mice. This suggests that prime-boost regimens combining adjuvanted protein and low-seroprevalent chimpanzee adenoviral vectors represent an attractive vaccination strategy for clinical evaluation.