Gene expression profiles provide an opportunity to dissect the heterogeneity of solid tumors, including colon cancer, to improve prognosis and predict response to therapies. Bayesian binary regression methods were used to generate a signature of disease recurrence in patients with resected early stage colon cancer validated in an independent cohort. A 50-gene signature was developed that effectively distinguished early stage colon cancer patients with a low or high risk of disease recurrence. RT-PCR analysis of the 50-gene signature validated 9 of the top 10 differentially expressed genes. When applied to two independent validation cohorts of 55 and 73 patients, the 50-gene model accurately predicted recurrence. Standard Kaplan-Meier survival analysis confirmed the prognostic accuracy (P < 0.01, log rank), as did multivariate Cox proportional hazard models. We tested potential targeted therapeutic options for patients at high risk for disease recurrence and found a clinically important relationship between sensitivity to celecoxib, LY-294002 (PI3kinase inhibitor), retinol, and sulindac in colon cancer cell lines expressing the poor prognostic phenotype (P < 0.01, t test), which performed better than standard chemotherapy (5-FU and oxaliplatin). We present a genomic strategy in early stage colon cancer to identify patients at highest risk of recurrence. An ability to move beyond current staging by refining the estimation of prognosis in early stage colon cancer also has implications for individualized therapy.