Therapies that boost the anti-tumor responses of cytotoxic T lymphocytes (CTLs) have shown promise; however, clinical responses to the immunotherapeutic agents currently available vary considerably, and the molecular basis of this is unclear. We performed transcriptomic profiling of tumor-infiltrating CTLs from treatment-naive patients with lung cancer to define the molecular features associated with the robustness of anti-tumor immune responses. We observed considerable heterogeneity in the expression of molecules associated with activation of the T cell antigen receptor (TCR) and of immunological-checkpoint molecules such as 4-1BB, PD-1 and TIM-3. Tumors with a high density of CTLs showed enrichment for transcripts linked to tissue-resident memory cells (T_RM cells), such as CD103, and CTLs from CD103^hi tumors displayed features of enhanced cytotoxicity. A greater density of T_RM cells in tumors was predictive of a better survival outcome in lung cancer, and this effect was independent of that conferred by CTL density. Here we define the 'molecular fingerprint' of tumor-infiltrating CTLs and identify potentially new targets for immunotherapy.