Ebola virus (EBOV) causes severe and often fatal hemorrhagic fever in humans and nonhuman primates (NHPs). Currently, there are no licensed vaccines or therapeutics for human use. Recombinant vesicular stomatitis virus (rVSV)-based vaccine vectors, which encode an EBOV glycoprotein in place of the VSV glycoprotein, have shown 100% efficacy against homologous Sudan ebolavirus (SEBOV) or Zaire ebolavirus (ZEBOV) challenge in NHPs. In addition, a single injection of a blend of three rVSV vectors completely protected NHPs against challenge with SEBOV, ZEBOV, the former Côte d'Ivoire ebolavirus, and Marburg virus. However, recent studies suggest that complete protection against the newly discovered Bundibugyo ebolavirus (BEBOV) using several different heterologous filovirus vaccines is more difficult and presents a new challenge. As BEBOV caused nearly 50% mortality in a recent outbreak any filovirus vaccine advanced for human use must be able to protect against this new species. Here, we evaluated several different strategies against BEBOV using rVSV-based vaccines. Groups of cynomolgus macaques were vaccinated with a single injection of a homologous BEBOV vaccine, a single injection of a blended heterologous vaccine (SEBOV/ZEBOV), or a prime-boost using heterologous SEBOV and ZEBOV vectors. Animals were challenged with BEBOV 29–36 days after initial vaccination. Macaques vaccinated with the homologous BEBOV vaccine or the prime-boost showed no overt signs of illness and survived challenge. In contrast, animals vaccinated with the heterologous blended vaccine and unvaccinated control animals developed severe clinical symptoms consistent with BEBOV infection with 2 of 3 animals in each group succumbing. These data show that complete protection against BEBOV will likely require incorporation of BEBOV glycoprotein into the vaccine or employment of a prime-boost regimen. Fortunately, our results demonstrate that heterologous rVSV-based filovirus vaccine vectors employed in the prime-boost approach can provide protection against BEBOV using an abbreviated regimen, which may have utility in outbreak settings.