The ability to monitor anti-tumor CD8+ T cell responses in the blood has tremendous therapeutic potential. Here, we used paired single-cell RNA and TCR sequencing to detect and characterize “tumor-matching” (TM) CD8+ T cells in the blood of mice with MC38 tumors or melanoma patients using the TCR as a molecular barcode. TM cells showed increased activation compared with nonmatching T cells in blood and were less exhausted than matching cells in tumors. Importantly, PD-1, which has been used to identify putative circulating anti-tumor CD8+ T cells, showed poor sensitivity for identifying TM cells. By leveraging the transcriptome, we identified candidate cell surface markers for TM cells in mice and patients and validated NKG2D, CD39, and CX3CR1 in mice. These data show that the TCR can be used to identify tumor-relevant cells for characterization, reveal unique transcriptional properties of TM cells, and develop marker panels for tracking and analysis of these cells.