Vaccines and therapies are urgently needed to address public health needs stemming from emerging pathogens and biological threat agents such as the filoviruses Ebola virus (EBOV) and Marburg virus (MARV). Here, we developed replication-competent vaccines against EBOV and MARV based on attenuated recombinant vesicular stomatitis virus vectors expressing either the EBOV glycoprotein or MARV glycoprotein. A single intramuscular injection of the EBOV or MARV vaccine elicited completely protective immune responses in nonhuman primates against lethal EBOV or MARV challenges. Notably, vaccine vector shedding was not detectable in the monkeys and none of the animals developed fever or other symptoms of illness associated with vaccination. The EBOV vaccine induced humoral and apparent cellular immune responses in all vaccinated monkeys, whereas the MARV vaccine induced a stronger humoral than cellular immune response. No evidence of EBOV or MARV replication was detected in any of the protected animals after challenge. Our data suggest that these vaccine candidates are safe and highly efficacious in a relevant animal model.