A better understanding of the distribution and functional capacity of CD4 T helper (Th) and CD8 T cytotoxic (Tc) cell subsets in the rectal mucosa (RM), a major site for HIV acquisition and replication, in adults is needed. In this study, we compared the distribution of Th and Tc cell subsets between blood and RM compartments in 62 HIV negative men, focusing primarily on IL-17-producing CD4 and CD8 T cells due to their importance in establishing and maintaining mucosal defenses, and examined associations between the frequencies of Th17 and Tc17 cell subsets and the availability of highly HIV-susceptible target cells in the RM. The RM exhibited a distinct immune cell composition comprised of higher frequencies of Th2, Th17, and Tc17 cells compared to the peripheral blood. The majority of Tc17 cells in RM were quadruple-cytokine producers (IL-17A+, IFN-γ+, TNF-α+, and IL4+), whereas most Th17 cells in blood and RM were single IL-17A producers or dual-cytokine producers (IL-17A+TNF-α+). In a separate cohort of 21 HIV positive men, we observed similar tissue distributions of Th and Tc cell subsets, although Tc17 cell frequencies in both blood and tissues were very low. Higher frequencies of multi-cytokine-producing Th17 and Tc17 cells in RM of HIV negative men positively correlated with increased mucosal HIV target cells, suggesting a need to further characterize the effector functions of these cells and their role in HIV acquisition and pathogenesis.