Background: The occurrence and progression of lung cancer are correlated with telomeres and telomerase. Telomere length is reduced in the majority of tumors, including lung cancers. Telomere length variations have been associated with lung cancer risk and may serve as therapeutic targets as well as predictive biomarkers for lung cancer. Nevertheless, the effects of telomere-associated genes on lung cancer prognosis have not been thoroughly studied. We aim to investigate the relationship between telomere-associated genes and lung cancer prognosis. Methods: The Cancer Genome Atlas and Genotype-Tissue Expression databases were used as training sets to build a predictive model. Three integrated Gene Expression Omnibus datasets served as validation sets. Using cluster consistency analysis and regression with the least absolute shrinkage and selection operator, we developed a telomere-related gene risk signature (TMGsig) based on 11 overall survival-related genes (RBBP8, PLK1, DSG2, HOXA7, ANAPC4, CSNK1E, SYAP1, ALDOA, PHF1, MUTYH, and PGS1). Results: The results indicated a negative outcome for the high-risk score group. Immunological microenvironment and somatic mutations differed between the high- and low-risk groups. A statistically significant difference existed between the low-risk and high-risk groups in terms of the expression levels of B cells and CD4 cells, and the risk score was essentially inversely linked with immune cell expression. Conclusions: TMGsig can predict outcomes in patients with lung adenocarcinoma.