CD8⁺ T cells infiltrating tumors are largely dysfunctional, but whether a subset maintains superior functionality remains ill defined. By high-dimensional single cell analysis of millions of CD8⁺ T cells from 53 individuals with lung cancer, we defined those subsets that are enriched in tumors compared with cancer-free tissues and blood. Besides exhausted and activated cells, we identified CXCR5⁺ TIM-3^– CD8⁺ T cells with a partial exhausted phenotype, while retaining gene networks responsible for stem-like plasticity and cytotoxicity, as revealed by single cell sequencing of the whole transcriptome. Ex vivo, CXCR5⁺ TIM-3^– CD8⁺ T cells displayed enhanced self-renewal and multipotency compared with more differentiated subsets and were largely polyfunctional. Analysis of inhibitory and costimulatory receptors revealed PD-1, TIGIT, and CD27 as possible targets of immunotherapy. We thus demonstrate a hierarchy of differentiation in the context of T cell exhaustion in human cancer similar to that of chronically infected mice, which is further shown to disappear with disease progression.