Background: Tamoxifen significantly improves outcome for estrogen receptor-positive (ER+) breast cancer, but the 15-year recurrence rate remains 30%. The aim of this study was to identify gene profiles that accurately predicted the outcome of ER+ breast cancer patients who received adjuvant Tamoxifen mono-therapy. Methodology/Principal Findings: Post-menopausal breast cancer patients diagnosed no later than 2002, being ER+ as defined by >1% IHC staining and having a frozen tumor sample with >50% tumor content were included. Tumor samples from 108 patients treated with adjuvant Tamoxifen were analyzed for the expression of 59 genes using quantitative-PCR. End-point was clinically verified recurrence to distant organs or ipsilateral breast. Gene profiles were identified using a model building procedure based on conditional logistic regression and leave-one-out cross-validation, followed by a non-parametric bootstrap (1000x re-sampling). The optimal profiles were further examined in 5 previously-reported datasets containing similar patient populations that were either treated with Tamoxifen or left untreated (n = 623). Three gene signatures were identified, the strongest being a 2-gene combination of BCL2-CDKN1A, exhibiting an accuracy of 75% for prediction of outcome. Independent examination using 4 previously-reported microarray datasets of Tamoxifen-treated patient samples (n = 503) confirmed the potential of BCL2-CDKN1A. The predictive value was further determined by comparing the ability of the genes to predict recurrence in an additional, previously-published, cohort consisting of Tamoxifen-treated (n = 58, p = 0.015) and untreated patients (n = 62, p = 0.25). Conclusions/Significance: A novel gene expression signature predictive of outcome of Tamoxifen-treated patients was identified. The validation suggests that BCL2-CDKN1A exhibit promising predictive potential.