The results of the recent Step Study highlight a need to clarify the effects of pre-existing natural immunity to a vaccine vector on vaccine-induced T-cell responses. To investigate this interaction, we examined the relationship between pre-existing Ad5 immunity and T-cell cytokine response profiles in healthy, HIV-uninfected recipients of MRKAd5 HIV-1 gag vaccine (HVTN 050, ClinicalTrials.gov #NCT00849732). Participants were grouped by baseline Ad5 neutralizing antibody titer as either Ad5-seronegative (titer ≤18; n = 36) or Ad5-seropositive (titer >200; n = 34). Samples from vaccine recipients were analyzed for immune responses to either HIV-1 Gag peptide pools or Ad5 empty vector using an ex vivo assay that measures thirty cytokines in the absence of long-term culture. The overall profiles of cytokine responses to Gag and Ad5 had similar combinations of induced Th1- and Th2-type cytokines, including IFN-γ, IL-2, TNF-α, IP-10, IL-13, and IL-10, although the Ad5-specific responses were uniformly higher than the Gag-specific responses (p<0.0001 for 9 out of 11 significantly expressed analytes). At the peak response time point, PBMC from Ad5-seronegative vaccinees secreted significantly more IP-10 in response to Gag (p = 0.008), and significantly more IP-10 (p = 0.0009), IL-2 (p = 0.006) and IL-10 (p = 0.05) in response to Ad5 empty vector than PBMC from Ad5-seropositive vaccinees. Additionally, similar responses to the Ad5 vector prior to vaccination were observed in almost all subjects, regardless of Ad5 neutralizing antibody status, and the levels of secreted IFN-γ, IL-10, IL-1Ra and GM-CSF were blunted following vaccination. The cytokine response profile of Gag-specific T cells mirrored the Ad5-specific response present in all subjects before vaccination, and included a number of Th1- and Th2-associated cytokines not routinely assessed in current vaccine trials, such as IP-10, IL-10, IL-13, and GM-CSF. Together, these results suggest that vector-specific humoral responses may reduce vaccine-induced T-cell responses by previously undetected mechanisms.