CD8+ T cells play an important role in early HIV infection. However, HIV has the capacity to avoid specific CTL responses due to a high rate of mutation under selection pressure. Although the HIV proteins, gag and pol, are relatively conserved, these sequences generate low-affinity MHC-associated epitopes that are poorly immunogenic. Here, we applied an approach that enhanced the immunogenicity of low-affinity HLA-A2.1-binding peptides. The first position with tyrosine (P1Y) substitution enhanced the affinity of HLA-A2.1-associated peptides without altering their antigenic specificity. More importantly, P1Y variants efficiently stimulated in vivo native peptide-specific CTL that also recognized the corresponding naturally processed epitope. The potential to generate CTL against any low-affinity HLA-A2.1-associated peptide provides us with the necessary technique for identification of virus cryptic epitopes for development of peptide-based immunotherapy. Therefore, identification and modification of the cryptic epitopes of gal and pol provides promising candidates for HIV immunotherapy dependent upon efficient presentation by virus cells. Furthermore, this may be a breakthrough that overcomes the obstacle of immune escape caused by high rates of mutation. In this study, bioinformatics analysis was used to predict six low-affinity cryptic HIV gag and pol epitopes presented by HLA-A*0201. A HIV compound multi-CTL epitope gene was constructed comprising the gene encoding the modified cryptic epitope and the HIV p24 antigen, which induced a strong CD8+ T cell immune response regardless of the mutation. This approach represents a novel strategy for the development of safe and effective HIV prophylactic and therapeutic vaccines.