There exists a unique group of persons who are able to durably control HIV in the absence of therapy. The mechanisms of control in these persons remain poorly defined. In this study, we examined CD8⁺ T-cell responses in blood and rectal mucosa from 17 “elite controllers” (viral load < 75 copies/mL), 11 “viremic controllers” (75-2000 copies/mL), 14 noncontrollers (> 10 000 copies/mL), and 10 antiretroviral-treated persons (< 75 copies/mL). Production of interferon-γ, interleukin-2, tumor necrosis factor-α, macrophage inflammatory protein-1β, and CD107a by CD8⁺ T cells in response to HIV-1 Gag stimulation was measured using flow cytometry. Our hypothesis was that “polyfunctional” T cells producing multiple antiviral factors would be most abundant in mucosal tissues of HIV controllers. Mucosal CD8⁺ T-cell responses were significantly stronger and more complex in controllers than in antiretroviral-suppressed persons (P = .0004). The frequency of 4-function responses in rectal mucosa was higher in controllers than in noncontrollers and patients on therapy (P < .0001). Mucosal responses in controllers were frequently stronger and more complex than blood responses. These findings demonstrate that many controllers mount strong, complex HIV-specific T-cell responses in rectal mucosa. These responses may play an important role in mucosal immune surveillance, as suggested by their relative enrichment among persons who control HIV in the absence of therapy.