Introduction: Surgical procedure is the treatment of choice in early stage I lung adenocarcinoma. However, a considerable number of patients experience recurrence within the first 2 years after complete resection. Suitable prognostic biomarkers that identify patients at high risk of recurrence (who may probably benefit from adjuvant treatment) are still not available. This study aimed at identifying methylation markers for early recurrence that may become important tools for the development of new treatment modalities. Methods: Genome-wide DNA methylation profiling was performed on 30 stage I lung adenocarcinomas, comparing 14 patients with early metastatic recurrence with 16 patients with a long-term relapse-free survival period using methylated-CpG-immunoprecipitation followed by high-throughput next-generation sequencing. The differentially methylated regions between the two subgroups were validated for their prognostic value in two independent cohorts using the MassCLEAVE assay, a high-resolution quantitative methylation analysis. Results: Unsupervised clustering of patients in the discovery cohort on the basis of differentially methylated regions identified patients with shorter relapse-free survival (hazard ratio: 2.23; 95% confidence interval: 0.66–7.53; p = 0.03). In two validation cohorts, promoter hypermethylation of the long noncoding RNA PLUT was significantly associated with shorter relapse-free survival (hazard ratio: 0.54; 95% confidence interval: 0.31–0.93; p < 0.026) and could be reported as an independent prognostic factor in the multivariate Cox regression analysis. Conclusions: Promoter hypermethylation of the long noncoding RNA PLUT is predictive in patients with early stage I adenocarcinoma at high risk for early recurrence. Further studies are needed to validate its role in carcinogenesis and its use as a biomarker to facilitate patient selection and risk stratification.