Evidence indicates that cytotoxic T lymphocytes (CTLs) may be important in containing the spread of the human immunodeficiency virus (HIV) in the infected host. Although the use of recombinant viruses has been proposed as an approach to elicit protective immunity against HIV, the ability of recombinant viral constructs to elicit CD8+ CTL responses in higher primates has never been demonstrated. A live recombinant virus, vaccinia-simian immunodeficiency virus of macaques (SIVmac), was used to determine whether such a genetically restricted, T lymphocyte-mediated antiviral response could be generated in a primate. Vaccinia-SIVmac vaccination elicited an SIVmac Gag-specific, CD8+ CTL response in rhesus monkeys. These CTLs recognized a peptide fragment that spans residues 171 to 195 of the Gag protein. The rhesus monkey major histocompatibility complex (MHC) class I gene product restricting this CTL response was defined. Both the vaccinated and SIVmac-infected monkeys that shared this MHC class I gene product developed CTLs with the same Gag epitope specificity. These findings support the use of recombinant virus vaccines for the prevention of HIV infections in humans.