Zika virus (ZIKV) is a mosquito-borne flavivirus that has rapidly extended its geographic range around the world. Its association with abnormal fetal brain development, sexual transmission, and lack of a preventive vaccine have constituted a global health concern. Designing a safe and effective vaccine requires significant caution due to overlapping geographical distribution of ZIKV with dengue virus (DENV) and other flaviviruses, possibly resulting in more severe disease manifestations in flavivirus immune vaccinees such as Antibody-Dependent Enhancement (ADE, a phenomenon involved in pathogenesis of DENV, and a risk associated with ZIKV vaccines using the envelope proteins as immunogens). Here, we describe the development of an alternative vaccine strategy encompassing the expression of ZIKV non-structural-1 (NS1) protein from a clinically proven safe, Modified Vaccinia Ankara (MVA) vector, thus averting the potential risk of ADE associated with structural protein-based ZIKV vaccines. A single intramuscular immunization of immunocompetent mice with the MVA-ZIKV-NS1 vaccine candidate provided robust humoral and cellular responses, and afforded 100% protection against a lethal intracerebral dose of ZIKV (strain MR766). This is the first report of (i) a ZIKV vaccine based on the NS1 protein and (ii) single dose protection against ZIKV using an immunocompetent lethal mouse challenge model.