Zika virus (ZIKV) is a re-emerging mosquito-borne flavivirus that affects humans and can cause severe neurological complications, including Guillain-Barré syndrome and microcephaly. Since 2007 there have been three large outbreaks; the last and larger spread in the Americas in 2015. Actually, ZIKV is circulating in the Americas, Southeast Asia, and the Pacific Islands, and represents a potential pandemic threat. Given the rapid ZIKV dissemination and the severe neurological and teratogenic sequelae associated with ZIKV infection, the development of a safe and efficacious vaccine is critical. In this study, we have developed and characterized the immunogenicity and efficacy of a novel ZIKV vaccine based on the highly attenuated poxvirus vector modified vaccinia virus Ankara (MVA) expressing the ZIKV prM and E structural genes (termed MVA-ZIKV). MVA-ZIKV expressed efficiently the ZIKV structural proteins, assembled in virus-like particles (VLPs) and was genetically stable upon nine passages in cell culture. Immunization of mice with MVA-ZIKV elicited antibodies that were able to neutralize ZIKV and induced potent and polyfunctional ZIKV-specific CD8+ T cell responses that were mainly of an effector memory phenotype. Moreover, a single dose of MVA-ZIKV reduced significantly the viremia in susceptible immunocompromised mice challenged with live ZIKV. These findings support the use of MVA-ZIKV as a potential vaccine against ZIKV.