Influenza epidemic and pandemic strains cannot be predicted with certainty. Current vaccines elicit antibodies effective against specific strains, but new strategies are urgently needed for protection against unexpected strains. DNA vaccines encoding conserved antigens protect animals against diverse subtypes, but their potency needs improvement. We tested DNA prime-recombinant adenoviral boost immunization to nucleoprotein (NP). Strong antibody and T cell responses were induced. Protection against challenge was T cell-dependent and substantially more potent than DNA vaccination alone. Importantly, vaccination protected against lethal challenge with highly pathogenic H5N1 virus. Thus, gene-based vaccination with NP may contribute to protective immunity against diverse influenza viruses through its ability to stimulate cellular immunity.