Current influenza vaccines mainly induce strain-specific neutralizing antibodies and need to be updated each year, resulting in significant burdens on vaccine manufacturers and regulatory agencies. Genetic immunization strategies based on the highly conserved nucleoprotein (NP) of influenza have attracted great attention as NP could induce heterosubtypic immunity. It is unclear, however, whether different forms of vectors and/or vaccination regimens could have contributed to the previously reported discrepancies in the magnitude of protection of NP-based genetic vaccinations. Here, we evaluated a plasmid DNA vector (pNP) and a recombinant adenovirus vector (rAd-NP) containing the NP gene through various combinations of immunization regimens in mice. We found that pNP afforded only partial protection even after 4 injections, with full protection against lethal challenge achieved only with the fourth boost using rAd-NP. Alternatively, only two doses of rAd-NP delivered subcutaneously were needed to induce an enhanced immune response and completely protect the animals, a finding which, to our knowledge, has not been reported before.