Celiac disease (CD) is an autoimmune disease in which intestinal inflammation is induced by dietary gluten. The means through which gluten-specific CD4+ T cell activation culminates in intraepithelial T cell (T-IEL)-mediated intestinal damage remain unclear. Here, we performed multiplexed single-cell analysis of intestinal and gluten-induced peripheral blood T cells from patients in different CD states and healthy controls. Untreated, active, and potential CD were associated with an enrichment of activated intestinal T cell populations, including CD4+ follicular T helper (TFH) cells, regulatory T cells (Tregs), and natural CD8+ αβ and γδ T-IELs. Natural CD8+ αβ and γδ T-IELs expressing activating natural killer cell receptors (NKRs) exhibited a distinct TCR repertoire in CD and persisted in patients on a gluten-free diet without intestinal inflammation. Our data further show that NKR-expressing cytotoxic cells, which appear to mediate intestinal damage in CD, arise from a distinct NKR-expressing memory population of T-IELs. After gluten ingestion, both αβ and γδ T cell clones from this memory population of T-IELs circulated systemically along with gluten-specific CD4+ T cells and assumed a cytotoxic and activating NKR-expressing phenotype. Collectively, these findings suggest that cytotoxic T cells in CD are rapidly mobilized in parallel with gluten-specific CD4+ T cells after gluten ingestion.