Virus-specific cytotoxic T lymphocytes (CTL) with high levels of functional avidity have been associated with viral clearance in hepatitis C virus infection and with enhanced antiviral protective immunity in animal models. However, the role of functional avidity as a determinant of HIV-specific CTL efficacy remains to be assessed. Here we measured the functional avidities of HIV-specific CTL responses targeting 20 different, optimally defined CTL epitopes restricted by 13 different HLA class I alleles in a cohort comprising 44 HIV controllers and 68 HIV noncontrollers. Responses restricted by HLA-B alleles and responses targeting epitopes located in HIV Gag exhibited significantly higher functional avidities than responses restricted by HLA-A or HLA-C molecules (P = 0.0003) or responses targeting epitopes outside Gag (P < 0.0001). The functional avidities of Gag-specific and HLA-B-restricted responses were higher in HIV controllers than in noncontrollers (P = 0.014 and P = 0.018) and were not restored in HIV noncontrollers initiating antiretroviral therapy. T-cell receptor (TCR) analyses revealed narrower TCR repertoires in higher-avidity CTL populations, which were dominated by public TCR sequences in HIV controllers. Together, these data link the presence of high-avidity Gag-specific and HLA-B-restricted CTL responses with viral suppression in vivo and provide new insights into the immune parameters that mediate spontaneous control of HIV infection.