Engendering cytotoxic T-lymphocyte (CTL) responses is likely to be an important goal of HIV vaccines. However, CTLs select for viral variants that escape immune detection. Maintenance of such escape variants in human populations could pose an obstacle to HIV vaccine development. We first observed that escape mutations in a heterogeneous simian immunodeficiency virus (SIV) isolate were lost upon passage to new animals. We therefore infected macaques with a cloned SIV bearing escape mutations in three immunodominant CTL epitopes, and followed viral evolution after infection. Here we show that each mutant epitope sequence continued to evolve in vivo, often re-establishing the original, CTL-susceptible sequence. We conclude that escape from CTL responses may exact a cost to viral fitness. In the absence of selective pressure upon transmission to new hosts, these original escape mutations can be lost. This suggests that some HIV CTL epitopes will be maintained in human populations.