Cytotoxic T Lymphocytes (CTLs) play a central role in controlling HIV-replication. Although numerous CTL epitopes have been described, most are in subtype B or C infection. Little is known about CTL responses in CRF01_AE infection. Gag CTL responses were investigated in a cohort of 137 treatment-naïve HIV-1 infected Thai patients with high CD4+ T cell counts, using gIFN Enzyme-Linked Immunospot (ELISpot) assays with 15-mer overlapping peptides (OLPs) derived from locally dominant CRF01_AE Gag sequences. 44 OLPs were recognized in 112 (81.8%) individuals. Both the breadth and magnitude of the CTL response, particularly against the p24 region, positively correlated with CD4+ T cell count and inversely correlated with HIV viral load. The breadth of OLP response was also associated with slower progression to antiretroviral therapy initiation. Statistical analysis and single peptide ELISpot assay identified at least 17 significant associations between reactive OLP and HLA in 12 OLP regions; 6 OLP-HLA associations (35.3%) were not compatible with previously reported CTL epitopes, suggesting that these contained new CTL Gag epitopes. A substantial proportion of CTL epitopes in CRF01_AE infection differ from subtype B or C. However, the pattern of protective CTL responses is similar; Gag CTL responses, particularly against p24, control viral replication and slow clinical progression.