Ebola viruses are highly pathogenic viruses that cause outbreaks of hemorrhagic fever in humans and other primates. To meet the need for a vaccine against the several types of Ebola viruses that cause human diseases, we developed a multivalent vaccine candidate (EBO7) that expresses the glycoproteins of Zaire ebolavirus (ZEBOV) and Sudan ebolavirus (SEBOV) in a single complex adenovirus-based vector (CAdVax). We evaluated our vaccine in nonhuman primates against the parenteral and aerosol routes of lethal challenge. EBO7 vaccine provided protection against both Ebola viruses by either route of infection. Significantly, protection against SEBOV given as an aerosol challenge, which has not previously been shown, could be achieved with a boosting vaccination. These results demonstrate the feasibility of creating a robust, multivalent Ebola virus vaccine that would be effective in the event of a natural virus outbreak or biological threat.