Previous studies have suggested that polyfunctional mucosal CD8(+) T-cell responses may be a correlate of protection in HIV controllers. Mucosal T-cell breadth and/or specificity may also contribute to defining protective responses. In this study, rectal CD8(+) T-cell responses to HIV Gag, Env, and Nef were mapped at the peptide level in four subject groups: elite controllers (n = 16; viral load [VL], <75 copies/ml), viremic controllers (n = 14; VL, 75 to 2,000 copies/ml), noncontrollers (n = 14; VL, >10,000 copies/ml), and antiretroviral-drug-treated subjects (n = 8; VL, <75 copies/ml). In all subject groups, immunodominant CD8(+) T-cell responses were generally shared by blood and mucosa, although there were exceptions. In HIV controllers, responses to HLA-B27- and HLA-B57-restricted epitopes were common to both tissues, and their magnitude (in spot-forming cells [SFC] per million) was significantly greater than those of responses restricted by other alleles. Furthermore, peptides recognized by T cells in both blood and rectal mucosa, termed "concordant," elicited higher median numbers of SFC than discordant responses. In magnitude as well as breadth, HIV Gag-specific responses, particularly those targeting p24 and p7, dominated in controllers. Responses in noncontrollers were more evenly distributed among epitopes in Gag, Env, and Nef. Viremic controllers showed significantly broader mucosal Gag-specific responses than other groups. Taken together, these findings demonstrate that (i) Gag-specific responses dominate in mucosal tissues of HIV controllers; (ii) there is extensive overlap between CD8(+) T cells in blood and mucosal tissues, with responses to immunodominant epitopes generally shared by both sites; and (iii) mucosal T-cell response breadth alone cannot account for immune control.