A prophylactic vaccine for HIV-1 will probably require the induction and maintenance of both humoral and cellular immunity. One current strategy to achieve such long term immune responses is a prime-boost vaccination approach using a DNA priming inoculation, followed by recombinant viral boost. In this report we use a novel prime-boost approach in which the priming injections consist of recombinant HIV-1 Gag protein mixed with cytosine phosphate guanosine oligodeoxynucleotide (CpG ODN), followed by recombinant adenoviral boost expressing HIV-1 Gag. Analysis of the immune responses indicates that HIV-1 Gag protein plus CpG ODN immunization alone induces potent humoral as well as Th1 and CD8+ T cell responses. Boosting with recombinant adenovirus strikingly enhances CD8+, but not Th1, T cell responses, resulting in CD8+ T cell responses far greater in magnitude than Th1 responses. Furthermore, the Th1 and CD8+ T cell responses following prime-boost immunization were seen in both lymphoid and peripheral mucosal organs and were sustained over several months. Together, these data suggest a new immunization approach for elicitation of long term humoral and cellular immune responses.