A safe and effective HIV-1 vaccine is urgently needed to control the worldwide AIDS epidemic. Traditional methods of vaccine development have been frustratingly slow, and it is becoming increasingly apparent that radical new approaches may be required. Computational and mathematical approaches, combined with evolutionary reasoning, may provide new insights for the design of an efficacious AIDS vaccine. Here, we used codon-based substitution models and maximum-likelihood (ML) methods to identify positively selected sites that are likely to be involved in the immune control of HIV-1. Analysis of subtypes B and C revealed widespread adaptive evolution. Positively selected amino acids were detected in all nine HIV-1 proteins, including Env. Of particular interest was the high level of positive selection within the C-terminal regions of the immediate-early regulatory proteins, Tat and Rev. Many of the amino acid replacements were associated with the emergence of novel (or alternative) myristylation and casein kinase II (CKII) phosphorylation sites. The impact of these changes on the conformation and antigenicity of Tat and Rev remains to be established. In rhesus macaques, a single CTL-associated amino substitution in Tat has been linked to escape from acute SIV infection. Understanding the relationship between host-driven positive selection and antigenic variation may lead to the development of novel vaccine strategies that preempt the escape process.