In lung cancer immunotherapy, biomarkers to guide clinical decisions are limited. We now explore whether the detailed immunophenotyping of circulating peripheral blood mononuclear cells (PBMCs) can predict the efficacy of anti-PD-1 immunotherapy in patients with advanced non-small-cell lung cancer (NSCLC). We determined 107 PBMCs subpopulations in a prospective cohort of NSCLC patients before starting single-agent anti-PD-1 immunotherapy (study group), analyzed by flow cytometry. As a control group, we studied patients with advanced malignancies before initiating non-immunotherapy treatment. The frequency of PBMCs was correlated with treatment outcome. Patients were categorized as having either high or low expression for each biomarker, defined as those above the 55th or below the 45th percentile of the overall marker expression within the cohort. In the study group, three subpopulations were associated with significant differences in outcome: high pretreatment levels of circulating CD4+CCR9+, CD4+CCR10+, or CD8+CXCR4+ T cells correlated with poorer overall survival (15.7 vs. 35.9 months, HR 0.16, p = 0.003; 22.0 vs. NR months, HR 0.10, p = 0.003, and 22.0 vs. NR months, HR 0.29, p = 0.02). These differences were specific to immunotherapy-treated patients. High baseline levels of circulating T cell subpopulations related to tissue lymphocyte recruitment are associated with poorer outcomes of immunotherapy-treated advanced NSCLC patients.