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 together with multiplex tissue imaging to assess spatial cell distribution, 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. Comparing single tumor cells with adjacent normal tissue and blood from patients with lung adenocarcinoma charts early changes in tumor immunity and provides insights to guide immunotherapy design.