Because of the high prevalence of adenovirus (Ad) infections in humans, it is believed that pre-existing Ad-neutralizing antibodies (vector immunity) may negatively impact the immune response to vaccine antigens when delivered by human Ad (HAd) vectors. In order to evaluate whether bovine Ad subtype 3 (BAd3), a non-HAd vector, can effectively elude high levels of pre-existing vector immunity, naïve and HAd serotype 5 (HAd)-primed mice were immunized with BAd-H5HA [BAd3 vector expressing the hemagglutinin (HA) gene from H5N1 influenza virus]. Even in the presence of very high levels of HAd-specific neutralizing antibody, no significant reductions in HA-specific humoral and cell-mediated immune (CMI) responses were observed in HAd-primed mice immunized with BAd-H5HA. In naïve mice immunized with HAd-H5HA (HAd5 vector expressing H5N1 HA) and boosted with BAd-H5HA, the humoral responses elicited were significantly higher (P < 0.01) than with either HAd-H5HA or BAd-H5HA alone, while the CMI responses were comparable in the groups. This finding underlines the importance of a heterologous prime-boost approach for achieving an enhanced immune response. The immunization of naïve or HAd-primed mice with BAd-H5HA bestowed full protection from morbidity and mortality following a potentially lethal challenge with A/Hong Kong/483/97. These results demonstrate the importance of BAd vectors as an alternate or supplement to HAd vectors for influenza pandemic preparedness.