Infection with Zika virus (ZIKV) is commonly mild in humans but has been associated with alarming negative health outcomes including Guillain-Barré syndrome in adults and microcephaly in fetuses. As such, developing a vaccine for ZIKV is a global public health priority. Recombinant vesicular stomatitis virus (VSV) expressing the Ebola virus (EBOV) glycoprotein (GP) has been successfully used as a vaccine platform in the past. In this study, two novel VSV-ZIKV vaccines were generated utilizing the favorable immune targeting of the existing VSV-EBOV vector. In addition to the EBOV GP, these new vaccines express the full-length pre-membrane and envelope proteins or pre-membrane and truncated soluble envelope proteins as antigens. Efficacy testing of both of the VSV vectors against ZIKV was conducted in IFNAR-/- mice and resulted in uniform protection when a single dose was administered 28 days prior to lethal challenge. Furthermore, this vaccine is fast-acting and can uniformly protect mice from lethal disease when administered as late as 3 days prior to ZIKV challenge. Thus, VSV-ZIKV vectors are promising vaccine candidates and should move forward along the licensure pathway.