Mice were immunized with Adenovirus expressing the H1-con, H2-con, H3-con and H5-con HA consensus genes in combination (multivalent) and compared to mice immunized with the traditional 2010-2011 FluZone and FluMist seasonal vaccines. Immunized mice were challenged with 10-100 MLD50 of H1N1, H3N1, H3N2 and H5N1 influenza viruses. The traditional vaccines induced robust levels of HA inhibition (HI) titers, but failed to protect against five different heterologous lethal influenza challenges. Conversely, the multivalent consensus vaccine (1 × 1010 virus particles (vp)/mouse) induced protective HI titers of ≥40 against 8 of 10 influenza viruses that represent a wide degree of divergence within the HA subtypes and protected 100% of mice from 8 of 9 lethal heterologous influenza virus challenges. The vaccine protection was dose dependent, in general, and a dose as low as 5 × 107 vp/mouse still provided 100% survival against 7 of 9 lethal heterologous influenza challenges. These data indicate that very low doses of Adenovirus-vectored consensus vaccines induce superior levels of immunity against a wide divergence of influenza subtypes as compared to traditional vaccines. These doses are scalable and translatable to humans and may provide the foundation for complete and long-lasting anti-influenza immunity.