We compared the human immunodeficiency virus type 1 (HIV-1)-specific cellular immune responses elicited in nonhuman primates by HIV-1 gag-expressing replication-defective adenovirus serotype 5 (Ad5) or poxvirus vectors, used either alone or in combination with each other. The responses arising from a heterologous Ad5 priming-poxvirus boosting regimen were significantly greater than those elicited by homologous regimens with the individual vectors or by a heterologous poxvirus priming-Ad5 boosting regimen. The heterologous Ad5 priming-poxvirus boosting approach may have potential utility in humans as a means of inducing high levels of cellular immunity.