BACKGROUND: The sudden emergence of novel influenza viruses is a global public health concern. Conventional influenza vaccines targeting the highly variable surface glycoproteins hemagglutinin and neuraminidase must antigenically match the emerging strain to be effective. In contrast, "universal" vaccines targeting conserved viral components could be used regardless of viral strain or subtype. Previous approaches to universal vaccination have required protracted multi-dose immunizations. Here we evaluate a single dose universal vaccine strategy using recombinant adenoviruses (rAd) expressing the conserved influenza virus antigens matrix 2 and nucleoprotein. METHODOLOGY/PRINCIPAL FINDINGS: In BALB/c mice, administration of rAd via the intranasal route was superior to intramuscular immunization for induction of mucosal responses and for protection against highly virulent H1N1, H3N2, or H5N1 influenza virus challenge. Mucosally vaccinated mice not only survived, but had little morbidity and reduced lung virus titers. Protection was observed as early as 2 weeks post-immunization, and lasted at least 10 months, as did antibodies and lung T cells with activated phenotypes. Virus-specific IgA correlated with but was not essential for protection, as demonstrated in studies with IgA-deficient animals. CONCLUSION/SIGNIFICANCE: Mucosal administration of NP and M2-expressing rAd vectors provided rapid and lasting protection from influenza viruses in a subtype-independent manner. Such vaccines could be used in the interval between emergence of a new virus strain and availability of strain-matched vaccines against it. This strikingly effective single-dose vaccination thus represents a candidate off-the-shelf vaccine for emergency use during an influenza pandemic.