Prediction of cancer progression after radical prostatectomy is one of the most challenging problems in the management of prostate cancer. Gene-expression profiling is widely used to identify genes associated with such progression. Usually candidate genes are identified according to a gene-by-gene comparison of expression. Recent reports suggested that relative expression of a gene pair more efficiently predicts cancer progression than single-gene analysis does. The top-scoring pair (TSP) algorithm classifies phenotypes according to the relative expression of a pair of genes. We applied the TSP approach to predict, which patients would experience systemic tumor progression after radical prostatectomy. Relative expression of TPD52L2/SQLE and CEACAM1/BRCA1 gene pairs identified those patients with more than 99% specificity but relatively low sensitivity (approximately 10%). These two gene pairs were validated in three independent data sets. In addition, combining two pairs of genes improved sensitivity without compromising specificity. Functional annotation of the TSP genes showed that they cluster by a limited number of biological functions and pathways, suggesting that relatively lower expression of genes from specific pathways can predict cancer progression. In conclusion, comparative analysis of the expression of two genes may be a simple and effective classifier for prediction of prostate cancer progression. In summary, the TSP approach can be used to identify patients whose prostate cancer will progress after they undergo radical prostatectomy. Two gene pairs can predict which men would experience progression to the metastatic form of the disease. However, because our analysis was based on a relatively small number of genes, a larger study will be needed to identify the best predictors of disease outcome overall.