The prevalence of preexisting immunity to adenoviruses in the majority of the human population might adversely impact the development of adaptive immune responses against adenovirus vector-based vaccines. To address this issue, we primed BALB/c mice either intranasally (i.n.) or intramuscularly (i.m.) with varying doses of wild type (WT) human adenovirus subtype 5 (HAd5). Following the development of immunity against HAd5, we immunized animals via the i.n. or i.m. route of inoculation with a HAd vector (HAd-HA-NP) expressing the hemagglutinin (HA) and nucleoprotein (NP) of A/Vietnam/1203/04 (H5N1) influenza virus. The immunogenicity and protection results suggest that low levels of vector immunity (<520 virus-neutralization titer) induced by priming mice with up to 10(7) plaque forming units (p.f.u.) of HAd-WT did not adversely impact the protective efficacy of the vaccine. Furthermore, high levels of vector immunity (approximately 1500 virus-neutralization titer) induced by priming mice with 10(8) p.f.u. of HAd-WT were overcome by either increasing the vaccine dose or using alternate routes of vaccination. A further increase in the priming dose to 10(9) p.f.u. allowed only partial protection. These results suggest possible strategies to overcome the variable levels of human immunity against adenoviruses, leading to better utilization of HAd vector-based vaccines.