Nearly a third of the human population is at risk of infection with the four serotypes of dengue viruses, and it is estimated that more than 100 million infections occur each year. A licensed vaccine for dengue viruses has become a global health priority. A major challenge to developing a dengue vaccine is the necessity to produce fairly uniform protective immune responses to all four dengue virus serotypes. We have developed two bivalent dengue virus vaccines, using a complex adenovirus vector, by incorporating the genes expressing premembrane (prM) and envelope (E) proteins of dengue virus types 1 and 2 (dengue-1 and -2, respectively) (CAdVax-Den12) or dengue-3 and -4 (CAdVax-Den34). Rhesus macaques were vaccinated by intramuscular inoculation of a tetravalent dengue vaccine formulated by combining the two bivalent vaccine constructs. Vaccinated animals produced high-titer antibodies that neutralized all four serotypes of dengue viruses in vitro. The ability of the vaccine to induce rapid, as well as sustained, protective immune responses was examined with two separate live-virus challenges administered at 4 and 24 weeks after the final vaccination. For both of these virus challenge studies, significant protection from viremia was demonstrated for all four dengue virus serotypes in vaccinated animals. Viremia from dengue-1 and dengue-3 challenges was completely blocked, whereas viremia from dengue-2 and dengue-4 was significantly reduced, as well as delayed, compared to that of control-vaccinated animals. These results demonstrate that the tetravalent dengue vaccine formulation provides significant protection in rhesus macaques against challenge with all four dengue virus serotypes.