Human immunodeficiency virus type 1 (HIV-1) can evade immunity shortly after transmission to a new host but the clinical significance of this early viral adaptation in HIV infection is not clear. We present an analysis of sequence variation from a longitudinal cohort study of HIV adaptation in 189 acute seroconverters followed for up to 3 years. We measured the rates of variation within well-defined epitopes to determine associations with the HLA-linked hazard of disease progression. We found early reversion across both the gag and pol genes, with a 10-fold faster rate of escape in gag (2.2 versus 0.27 forward mutations/1,000 amino acid sites). For most epitopes (23/34), variation in the HLA-matched and HLA-unmatched controls was similar. For a minority of epitopes (8/34, and generally associated with HLA class I alleles that confer clinical benefit), new variants appeared early and consistently over the first 3 years of infection. Reversion occurred early at a rate which was HLA-dependent and correlated with the HLA class 1-associated relative hazard of disease progression and death (P = 0.0008), reinforcing the association between strong cytotoxic T-lymphocyte responses, viral fitness, and disease status. These data provide a comprehensive overview of viral adaptation in the first 3 years of infection. Our findings of HLA-dependent reversion suggest that costs are borne by some escape variants which may benefit the host, a finding contrary to a simple immune evasion paradigm. These epitopes, which are both strongly and frequently recognized, and for which escape involves a high cost to the virus, have the potential to optimize vaccine design.