Seasonal influenza is an annually severe crisis for global public health, and an ideal influenza vaccine is expected to provide broad protection against constantly drifted strains. Compared to highly flexible hemagglutinin (HA), increasing data have demonstrated that neuraminidase (NA) might be a potential target against influenza variants. In the present study, a series of genetic algorithm-based mosaic NA were designed, and then cloned into recombinant DNA and replication-defective Vesicular Stomatitis Virus (VSV) vector as a novel influenza vaccine candidate. Our Results showed that DNA prime/VSV boost strategy elicited a robust NA-specific Th1-dominated immune response, but the traditional inactivated influenza vaccine elicited a Th2-dominated immune response. More importantly, the superior NA-specific immunity induced by our strategy could confer both a full protection against lethal homologous influenza challenge and a partial protection against heterologous influenza infection. These findings will provide insights on designing NA-based universal vaccine strategy against influenza variants.