To guide the design of immunotherapy strategies for patients with early stage lung tumors, we developed a multiscale immune profiling strategy to map the immune landscape of early lung adenocarcinoma lesions to search for tumor-driven immune changes. Utilizing a barcoding method that allows a simultaneous single-cell analysis of the tumor, non-involved lung, and blood cells, we provide a detailed immune cell atlas of early lung tumors. We show that stage I lung adenocarcinoma lesions already harbor significantly altered T cell and NK cell compartments. Moreover, we identified changes in tumor-infiltrating myeloid cell (TIM) subsets that likely compromise anti-tumor T cell immunity. Paired single-cell analyses thus offer valuable knowledge of tumor-driven immune changes, providing a powerful tool for the rational design of immune therapies.