A major challenge in developing vaccines for emerging pathogens is their continued evolution and ability to escape human immunity. Therefore, an important goal of vaccine research is to advance vaccine candidates with sufficient breadth to respond to new outbreaks of previously undetected viruses. Ebolavirus (EBOV) vaccines have demonstrated protection against EBOV infection in nonhuman primates (NHP) and show promise in human clinical trials but immune protection occurs only with vaccines whose antigens are matched to the infectious challenge species. A 2007 hemorrhagic fever outbreak in Uganda demonstrated the existence of a new EBOV species, Bundibugyo (BEBOV), that differed from viruses covered by current vaccine candidates by up to 43% in genome sequence. To address the question of whether cross-protective immunity can be generated against this novel species, cynomolgus macaques were immunized with DNA/rAd5 vaccines expressing ZEBOV and SEBOV glycoprotein (GP) prior to lethal challenge with BEBOV. Vaccinated subjects developed robust, antigen-specific humoral and cellular immune responses against the GP from ZEBOV as well as cellular immunity against BEBOV GP, and immunized macaques were uniformly protected against lethal challenge with BEBOV. This report provides the first demonstration of vaccine-induced protective immunity against challenge with a heterologous EBOV species, and shows that Ebola vaccines capable of eliciting potent cellular immunity may provide the best strategy for eliciting cross-protection against newly emerging heterologous EBOV species.