Clinically, our ability to predict disease outcome for patients with early stage lung cancer is currently poor. To address this issue, tumour specimens were collected at surgery from non-small cell lung cancer (NSCLC) patients as part of the European Early Lung Cancer (EUELC) consortium. The patients were followed-up for three years post-surgery and patients who suffered progressive disease (PD, tumour recurrence, metastasis or a second primary) or remained disease-free (DF) during follow-up were identified. RNA from both tumour and adjacent-normal lung tissue was extracted from patients and subjected to microarray expression profiling. These samples included 36 adenocarcinomas and 23 squamous cell carcinomas from both PD and DF patients. The microarray data was subject to a series of systematic bioinformatics analyses at gene, network and transcription factor levels. The focus of these analyses was 2-fold: firstly to determine whether there were specific biomarkers capable of differentiating between PD and DF patients, and secondly, to identify molecular networks which may contribute to the progressive tumour phenotype. The experimental design and analyses performed permitted the clear differentiation between PD and DF patients using a set of biomarkers implicated in neuroendocrine signalling and allowed the inference of a set of transcription factors whose activity may differ according to disease outcome. Potential links between the biomarkers, the transcription factors and the genes p21/CDKN1A and Myc, which have previously been implicated in NSCLC development, were revealed by a combination of pathway analysis and microarray meta-analysis. These findings suggest that neuroendocrine-related genes, potentially driven through p21/CDKN1A and Myc, are closely linked to whether or not a NSCLC patient will have poor clinical outcome.