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.