Several human and nonhuman adenovirus (AdV) vectors including bovine AdV type 3 (BAdV-3) were developed as gene delivery vectors to supplement and/or elude human AdV (HAdV)-specific neutralizing antibodies (vector immunity). Here we evaluated the vaccine immunogenicity and efficacy of BAdV-3 vector (BAd-H5HA) expressing hemagglutinin (HA) of a H5N1 influenza virus in a dose escalation study in mice with the intranasal (IN) or intramuscular (IM) route of inoculation in comparison with the HAdV type C5 (HAdV-C5) vector (HAd-H5HA) expressing HA of a H5N1 influenza virus. Dose-related increases in the immune responses were clearly noticeable. A single IM inoculation with BAd-H5HA resulted in enhanced cellular immune responses compared with that of HAd-H5HA and conferred complete protection following challenge with a heterologous H5N1 virus at the dose of 3 × 107 plaque-forming units (PFUs), whereas a significant amount of influenza virus was detected in the lungs of mice immunized with 1 × 108 PFUs of HAd-H5HA. Similarly, compared with that of HAd-H5HA, a single IN inoculation with BAd-H5HA produced significantly enhanced humoral (HA-specific immunoglobulin [IgG] and its subclasses, as well as HA-specific IgA) and cellular immune responses, and conferred complete protection following challenge with a heterologous H5N1 virus. Complete protection with BAd-H5HA was observed with the lowest vaccine dose (1 × 106 PFUs), but similar protection with HAd-H5HA was observed at the highest vaccine dose (1 × 108 PFUs). These results suggest that at least 30-fold dose sparing can be achieved with BAd-H5HA vector compared with HAd-H5HA vaccine vector.