One of the main challenges of lung cancer research is identifying patients at high risk for recurrence after surgical resection. Simple, accurate, and reproducible methods of evaluating individual risks of recurrence are needed. Based on a combined analysis of time-to-recurrence data, censoring information, and microarray data from a set of 138 patients, we selected statistically significant genes thought to be predictive of disease recurrence. The number of genes was further reduced by eliminating those whose expression levels were not reproducible by real-time quantitative PCR. Within these variables, a recurrence prediction model was constructed using Cox proportional hazard regression and validated via two independent cohorts (n = 56 and n = 59). After performing a log-rank test of the microarray data and successively selecting genes based on real-time quantitative PCR analysis, the most significant 18 genes had P values of <0.05. After subsequent stepwise variable selection based on gene expression information and clinical variables, the recurrence prediction model consisted of six genes (CALB1, MMP7, SLC1A7, GSTA1, CCL19, and IFI44). Two pathologic variables, pStage and cellular differentiation, were developed. Validation by two independent cohorts confirmed that the proposed model is significantly accurate (P = 0.0314 and 0.0305, respectively). The predicted median recurrence-free survival times for each patient correlated well with the actual data. We have developed an accurate, technically simple, and reproducible method for predicting individual recurrence risks. This model would potentially be useful in developing customized strategies for managing lung cancer.