Molecular epidemiology studies have identified HLA-B*58:01 as a protective HIV allele. However, not all B*58:01-expressing persons exhibit slow HIV disease progression. We followed six HLA-B*58:01-positive, HIV subtype C-infected individuals for up to 31 months from the onset of infection and observed substantial variability in their clinical progression despite comparable total breadths of T cell responses. We therefore investigated additional immunological and virological factors that could explain their different disease trajectories. Cytotoxic T-lymphocyte (CTL) responses during acute infection predominantly targeted the TW10 and KF9 epitopes in p24Gag and Nef, respectively. Failure to target the TW10 epitope in one B*58:01-positive individual was associated with low CD4 counts and rapid disease progression. Among those targeting TW10, escape mutations arose within 2 to 15 weeks of infection. Rapid escape was associated with preexisting compensatory mutations in the transmitted viruses, which were present at a high frequency (69%) in the study population. At 1 year post infection, B*58:01-positive individuals who targeted and developed escape mutations in the TW10 epitope (n=5) retained significantly higher CD4 counts (P=0.04), but not lower viral loads, than non-B*58:01-positive individuals (n=17). The high population-level frequency of these compensatory mutations may be limiting the protective effect of the B*58:01 allele.