A recent clinical trial of a T-cell-based AIDS vaccine delivered with recombinant adenovirus type 5 (rAd5) vectors showed no efficacy in lowering viral load and was associated with increased risk of human immunodeficiency virus type 1 (HIV-1) infection. Preexisting immunity to Ad5 in humans could therefore affect both immunogenicity and vaccine efficacy. We hypothesized that vaccine-induced immunity is differentially affected, depending on whether subjects were exposed to Ad5 by natural infection or by vaccination. Serum samples from vaccine trial subjects receiving a DNA/rAd5 AIDS vaccine with or without prior immunity to Ad5 were examined for the specificity of their Ad5 neutralizing antibodies and their effect on HIV-1 immune responses. Here, we report that rAd5 neutralizing antibodies were directed to different components of the virion, depending on whether they were elicited by natural infection or vaccination in HIV vaccine trial subjects. Neutralizing antibodies elicited by natural infection were directed largely to the Ad5 fiber, while exposure to rAd5 through vaccination elicited antibodies primarily to capsid proteins other than fiber. Notably, preexisting immunity to Ad5 fiber from natural infection significantly reduced the CD4 and CD8 cell responses to HIV Gag after DNA/rAd5 vaccination. The specificity of Ad5 neutralizing antibodies therefore differs depending on the route of exposure, and natural Ad5 infection compromises Ad5 vaccine-induced immunity to weak immunogens, such as HIV-1 Gag. These results have implications for future AIDS vaccine trials and the design of next-generation gene-based vaccine vectors.