HIV-specific cytotoxic T lymphocytes (CTLs) play an important role in control of HIV infection. HLA class I molecules, which mediate recognition of HIV-infected cells by the CTLs, have great diversity. Some HLA class I molecules are well known to associate with HIV control. HIV escapes from the CTLs through amino acid mutations within CTL epitopes. The rapid and extensive spread of HIV escape mutants provides accumulation of the mutants at a population level, demonstrating strong evidence of HIV adaptation to HLA class I. In this review, we discuss the role of the CTLs in controlling HIV, the relationship between HLA alleles and HIV control, and the accumulation of HIV mutants selected by the CTLs at a population level.