Immunotherapies that block inhibitory checkpoint receptors on T cells have transformed the clinical care of patients with cancer. However, whether the T cell response to checkpoint blockade relies on reinvigoration of pre-existing tumor-infiltrating lymphocytes or on recruitment of novel T cells remains unclear. Here we performed paired single-cell RNA and T cell receptor sequencing on 79,046 cells from site-matched tumors from patients with basal or squamous cell carcinoma before and after anti-PD-1 therapy. Tracking T cell receptor clones and transcriptional phenotypes revealed coupling of tumor recognition, clonal expansion and T cell dysfunction marked by clonal expansion of CD8+CD39+ T cells, which co-expressed markers of chronic T cell activation and exhaustion. However, the expansion of T cell clones did not derive from pre-existing tumor-infiltrating T lymphocytes; instead, the expanded clones consisted of novel clonotypes that had not previously been observed in the same tumor. Clonal replacement of T cells was preferentially observed in exhausted CD8+ T cells and evident in patients with basal or squamous cell carcinoma. These results demonstrate that pre-existing tumor-specific T cells may have limited reinvigoration capacity, and that the T cell response to checkpoint blockade derives from a distinct repertoire of T cell clones that may have just recently entered the tumor.