Non-small cell lung cancer (NSCLC), which consists mainly of lung adenocarcinoma (LUAD) and lung squamous cell carcinoma (LUSC), are the leading cause of cancer deaths worldwide. In this study, we performed a comprehensive analysis of the tumor microenvironmental and genetic factors to identify prognostic biomarkers for NSCLC. We evaluated the immune and stromal scores of patients with LUAD and LUSC using data from The Cancer Genome Atlas database with the ESTIMATE algorithm. Based on these scores, the differentially expressed genes were obtained and immune-related prognostic genes were identified. Functional analysis and protein-protein interaction network further revealed the immune-related biological processes in which these genes participated. Additionally, 22 subsets of tumor-infiltrating immune cells (TIICs) in the tumor microenvironment were analyzed with the CIBERSORT algorithm. Finally, we validated these valuable genes using an independent cohort from the Gene Expression Omnibus database. The associations of the immune and stromal scores with patients’ clinical characteristics and prognosis were positive in LUAD but negative in LUSC and the correlations of TIICs with clinical characteristics were clarified. Several differentially expressed genes were identified to be potential immune-related prognostic genes. This study comprehensively analyzed the tumor microenvironment and presented immune-related prognostic biomarkers for NSCLC.