Conventional influenza vaccines need to be designed and manufactured yearly. However, they occasionally provide poor protection owing to antigenic mismatch. Hence, there is an urgent need to develop universal vaccines against influenza virus. Using nucleoprotein (NP) and extracellular domain of matrix protein 2 (M2e) genes from the influenza A virus A/Beijing/30/95 (H3N2), we constructed four recombinant vaccinia virus-based influenza vaccines carrying NP fused with one or four copies of M2e genes in different orders. The recombinant vaccinia viruses were used to immunize BALB/C mice. Humoral and cellular responses were measured, and then the immunized mice were challenged with the influenza A virus A/Puerto Rico/8/34 (PR8). NP-specific humoral response was elicited in mice immunized with recombinant vaccinia viruses carrying full-length NP, while robust M2e-specific humoral response was elicited only in the mice immunized with recombinant vaccinia viruses carrying multiple copies of M2e. All recombinant viruses elicited NP- and M2e-specific cellular immune responses in mice. Only immunization with RVJ-4M2eNP induced remarkably higher levels of IL-2 and IL-10 cytokines specific to M2e. Furthermore, RVJ-4M2eNP immunization provided the highest cross-protection in mice challenged with 20 MLD50 of PR8. Therefore, the cross-protection potentially correlates with both NP and M2e-specific humoral and cellular immune responses induced by RVJ-4M2eNP, which expresses a fusion antigen of full-length NP preceded by four M2e repeats. These results suggest that the rational fusion of NP and multiple M2e antigens is critical toward inducing protective immune responses, and the 4M2eNP fusion antigen may be employed to develop a universal influenza vaccine.