Relapse rates in surgically resected non-small-cell lung cancer (NSCLC) patients are between 30% and 45% within five years of diagnosis, which shows the clinical need to identify those patients at high risk of recurrence. The eighth TNM staging system recently refined the classification of NSCLC patients and their associated prognosis, but molecular biomarkers could improve the heterogeneous outcomes found within each stage. Here, using two independent cohorts (MDA and CIMA-CUN) and the eighth TNM classification, we show that TMPRSS4 protein expression is an independent prognostic factor in NSCLC, particularly for patients at stage I: relapse-free survival (RFS) HR, 2.42 (95% CI, 1.47–3.99), p < 0.001; overall survival (OS) HR, 1.99 (95% CI, 1.25–3.16), p = 0.004). In stage IA, high levels of this protein remained associated with worse prognosis (p = 0.002 for RFS and p = 0.001 for OS). As TMPRSS4 expression is epigenetically regulated, methylation status could be used in circulating tumor DNA from liquid biopsies to monitor patients. We developed a digital droplet PCR (ddPCR) method to quantify absolute copy numbers of methylated and unmethylated CpGs within the TMPRSS4 and SHOX2 (as control) promoters in plasma and bronchoalveolar lavage (BAL) samples. In case-control studies, we demonstrated that TMPRSS4 hypomethylation can be used as a diagnostic tool in early stages, with an AUROC of 0.72 (p = 0.008; 91% specificity and 52% sensitivity) for BAL and 0.73 (p = 0.015; 65% specificity and 90% sensitivity) for plasma, in early stages. In conclusion, TMPRSS4 protein expression can be used to stratify patients at high risk of relapse/death in very early stages NSCLC patients. Moreover, analysis of TMPRSS4 methylation status by ddPCR in blood and BAL is feasible and could serve as a non-invasive biomarker to monitor surgically resected patients.