Preexisting immunity to adenovirus serotype 5 (Ad5) diminishes immune responses to vaccines using Ad5 as a vector. Alternate Ad serotypes as vaccine vectors might overcome Ad5-specific neutralizing antibodies and enhance immune responses in populations with a high prevalence of Ad5 immunity. To test this hypothesis, healthy human immunodeficiency virus (HIV)-seronegative adults were enrolled in a blinded, randomized, dose-escalating, placebo-controlled study. In part A, subjects with baseline Ad6 titers of ≤18 received the Merck Ad6 (MRKAd6) HIV type 1 (HIV-1) trigene vaccine at weeks 0, 4, and 26. In part B, subjects stratified by Ad5 titers (≤200 or >200) and Ad6 titers (≤18 or >18) received the MRKAd5-plus-MRKAd6 (MRKAd5+6) HIV-1 trigene vaccine at weeks 0, 4, and 26. Immunogenicity was assessed by an enzyme-linked immunospot (ELISPOT) assay at week 30. No serious adverse events occurred. MRKAd6 trigene vaccine recipients responded more often to Nef than to Gag or Pol. In part A, ELISPOT response rates to ≥2 vaccine antigens were 14%, 63%, and 71% at 109, 1010, and 1011 viral genomes (vg)/dose, respectively. All responders had positive Nef-specific ELISPOT results. In part B, Nef-ELISPOT response rates at 1010 vg/dose of the MRKAd5+6 trigene vaccine were 50% in the low-Ad5/low-Ad6 stratum (n = 8), 78% in the low-Ad5/high-Ad6 stratum (n = 9), 75% in the high-Ad5/low-Ad6 stratum (n = 8), and 44% in the high-Ad5/high-Ad6 stratum (n = 9). The MRKAd6 and MRKAd5+6 trigene vaccines elicited dose-dependent responses predominantly to Nef and were generally well tolerated, indicating that Ad6 should be considered a candidate vector for future vaccines. Although small sample sizes limit the conclusions that can be drawn from this exploratory study, combining two Ad vectors may be a useful vaccine strategy for circumventing isolated immunity to a single Ad serotype.