O ne of the major problems in management of prostate cancer is the lack of reliable genetic markers predicting the clinical course of the disease. We analyzed expression profiles of 12,625 transcripts in prostate tumors from patients with distinct clinical outcomes after therapy as well as metastatic human prostate cancer xenografts in nude mice. We identified small clusters of genes discriminating recurrent versus nonrecurrent disease with 90% and 75% accuracy in two independent cohorts of patients. We examined one group of samples (21 tumors) to discover the recurrence predictor genes and then validated the predictive power of these genes in a different set (79 tumors). Kaplan-Meier analysis demonstrated that recurrence predictor signatures are highly informative (P < 0.0001) in stratification of patients into subgroups with distinct relapse-free survival after therapy. A gene expression–based recurrence predictor algorithm was informative in predicting the outcome in patients with early-stage disease, with either high or low preoperative prostate-specific antigen levels and provided additional value to the outcome prediction based on Gleason sum or multiparameter nomogram. Overall, 88% of patients with recurrence of prostate cancer within 1 year after therapy were correctly classified into the poor-prognosis group. The identified algorithm provides additional predictive value over conventional markers of outcome and appears suitable for stratification of prostate cancer patients at the time of diagnosis into subgroups with distinct survival probability after therapy.