HIV evades CD8 T cell mediated pressure by viral escape mutations in targeted CD8 T cell epitopes. A viral escape mutation can lead to a decline of the respective CD8 T cell response. Our question was what happened after the decline of a CD8 T cell response and - in the case of viral escape - if a new CD8 T cell response towards the mutated antigen could be generated in a population not selected for certain HLA alleles. We studied 19 antiretroviral-naïve HIV-1 infected individuals with different disease courses longitudinally. A median number of 12 (range 2-24) CD8 T cell responses towards Gag and Nef were detected per study subject. A total of 30 declining CD8 T cell responses were studied in detail and viral sequence analyses showed amino acid changes in 25 (83%) of these. Peptide titration assays and definition of optimal CD8 T cell epitopes revealed 12 viral escape mutations with one de-novo response (8%). The de-novo response, however, showed less effector functions than the original CD8 T cell response. In addition we identified 4 shifts in immunodominance. For one further shift in immunodominance, the mutations occurred outside the optimal epitope and might represent processing changes. Interestingly, four adaptations to the virus (the de-novo response and 3 shifts in immunodominance) occurred in the group of chronically infected progressors. None of the subjects with adaptation to the changing virus carried the HLA alleles B57, B*58:01 or B27. Our results show that CD8 T cell responses adapt to the mutations of HIV. However it was limited to only 20% (5 out of 25) of the epitopes with viral sequence changes in a cohort not expressing protective HLA alleles.