Ebola virus (EBOV) causes a severe hemorrhagic fever for which there are currently no vaccines or effective treatments. While lethal human outbreaks have so far been restricted to sub-Saharan Africa, the potential exploitation of EBOV as a biological weapon cannot be ignored. Two species of EBOV, Sudan ebolavirus (SEBOV) and Zaire ebolavirus (ZEBOV), have been responsible for all of the deadly human outbreaks resulting from this virus. Therefore, it is important to develop a vaccine that can prevent infection by both lethal species. Here, we describe the bivalent cAdVaxE(GPs/z) vaccine, which includes the SEBOV glycoprotein (GP) and ZEBOV GP genes together in a single complex adenovirus-based vaccine (cAdVax) vector. Vaccination of mice with the bivalent cAdVaxE(GPs/z) vaccine led to efficient induction of EBOV-specific antibody and cell-mediated immune responses to both species of EBOV. In addition, the cAdVax technology demonstrated induction of a 100% protective immune response in mice, as all vaccinated C57BL/6 and BALB/c mice survived challenge with a lethal dose of ZEBOV (30,000 times the 50% lethal dose). This study demonstrates the potential efficacy of a bivalent EBOV vaccine based on a cAdVax vaccine vector design.