Recombinant viruses hold promise as vectors for vaccines to prevent infectious diseases with significant global health impacts. One of their major limitations is that preexisting anti-vector neutralizing antibodies can reduce T cell responses to the insert antigens; however, the impact of vector-specific cellular immunity on subsequent insert-specific T cell responses has not been assessed in humans. Here, we have identified and compared adenovirus-specific and HIV-specific T cell responses in subjects participating in two HIV-1 vaccine trials using a vaccine vectored by adenovirus serotype 5 (Ad5). Higher frequencies of pre-immunization adenovirus-specific CD4⁺ T cells were associated with substantially decreased magnitude of HIV-specific CD4⁺ T cell responses and decreased breadth of HIV-specific CD8⁺ T cell responses in vaccine recipients, independent of type-specific preexisting Ad5-specific neutralizing antibody titers. Further, epitopes recognized by adenovirus-specific T cells were commonly conserved across many adenovirus serotypes, suggesting that cross-reactivity of preexisting adenovirus-specific T cells can extend to adenovirus vectors derived from rare serotypes. These findings provide what we believe to be a new understanding of how preexisting viral immunity may impact the efficacy of vaccines under current evaluation for prevention of HIV, tuberculosis, and malaria.