Live attenuated vaccine vectors based on recombinant vesicular stomatitis viruses (rVSVs) expressing foreign antigens are highly effective vaccines in animal models. In this study, we report that an rVSV expressing influenza nucleoprotein (VSV NP) from the first position of the VSV genome induces robust anti-NP CD8 T cells in immunized mice. These CD8 T cells are phenotypically similar to those induced by natural influenza infection and are cytotoxic in vivo. Animals immunized with an rVSV expressing the influenza hemagglutinin (rVSV HA) were protected but still exhibited considerable morbidity after challenge. Animals receiving a cocktail vaccine of rVSV NP and rVSV HA had reduced pulmonary viral loads, less weight loss, and reduced clinical signs of illness after influenza virus challenge, relative to those vaccinated with rVSV HA alone. Influenza NP is a highly conserved antigen, and induction of protective anti-NP responses may be a productive strategy for generating heterologous protection against divergent influenza strains.