Lung cancer is the leading cause of cancer deaths worldwide. Clinical staging classification is generally insufficient to provide a reliable prognosis, particularly for early stages. In addition, prognostic factors are therefore needed to better forecast life expectancy and optimize adjuvant therapeutic strategy. Recent evidence indicates that alterations of the DNA replication program contribute to neoplasia from its early stages and that cancer cells are frequently exposed to endogenous replication stress. We therefore hypothesized that genes involved in the replication stress response may represent an under-explored source of biomarkers. Expressions of 77 DNA replication-associated genes implicated in different aspects of chromosomal DNA replication, including licensing, firing of origins, elongation, replication fork maintenance and recovery, lesion bypass and post-replicative repair were determined in primary tumors and adjacent normal tissues from 93 patients suffering from early-or mid-stage non-small cell lung cancer (NSCLC). We then investigated a statistically significant interaction between gene expressions and survival of early-stage NSCLC patients. The expression of five genes, that is, POLQ, PLK1, RAD51, CLASPIN and CDC6 was associated with overall, disease-free and relapse-free survival. The expression levels are independent of treatment and stage classification. Except RAD51, their prognostic role on survival persists after adjustment on age, sex, treatment, stage classification and conventional proliferation markers, with a hazard ratio of 36.3 for POLQ (95% CI 2.6–517.4, P= 0.008), 23.5 for PLK1 (95% CI 1.9–288.4, P= 0.01), 20.7 for CLASPIN (95% CI 1.5–275.9, P= 0.02) and 18.5 for CDC6 (95% CI 1.3–267.4, P= 0.03). We also show that a five-gene signature including POLQ, PLK1, RAD51, CLASPIN and CDC6 separates patients into low-and high-risk groups, with a hazard ratio of 14.3 (95% CI 5.1–40.3, P< 0.001). This ‘replication stress’ metamarker may be a reliable predictor of survival for NSCLC, and may also help understand the molecular mechanisms underlying tumor progression.