The diagnosis of breast cancer—including determination of prognosis and prediction—has been traditionally based on clinical and pathological characteristics such as tumor size, nodal status, and tumor grade. The decision-making process has been expanded by the recent introduction of molecular signatures. These signatures, however, have not reached the highest levels of evidence thus far. Yet they have been brought to clinical practice based on statistical significance in prospective as well as retrospective studies. Intriguingly, it has also been reported that most random sets of genes are significantly associated with disease outcome. These facts raise two highly relevant questions: What information gain do these signatures procure? How can one find a signature that is substantially better than a random set of genes? Our study addresses these questions. To address the latter question, we present a hybrid signature that joins the traditional approach with the molecular one by combining the Nottingham Prognostic Index with gene expressions in a data-driven fashion. To address the issue of information gain, we perform careful statistical analysis and comparison of the hybrid signature, gene expression lists of two commercially available tests as well as signatures selected at random, and introduce the Signature Skill Score—a simple measure to assess improvement on random signatures. Despite being based on in silico data, our research is designed to be useful for the decision-making process of oncologists and strongly supports association of random signatures with outcome. Although our study shows that none of these signatures can be considered as the main candidate for providing prognostic information, it also demonstrates that both the hybrid signature and the gene expression list of the OncotypeDx signature identify patients who may not require adjuvant chemotherapy. More importantly, we show that combining signatures substantially improves the identification of patients who do not need adjuvant chemotherapy.