Breast cancer is a heterogeneous disease whose evolution is difficult to predict by using classic histoclinical prognostic factors. Prognostic classification can benefit from molecular analyses such as large-scale expression profiling. Using immunohistochemistry on tissue microarrays, we have monitored the expression of 26 selected proteins in more than 1,600 cancer samples from 552 consecutive patients with early breast cancer. Both an unsupervised approach and a new supervised method were used to analyze these profiles. Hierarchical clustering identified relevant clusters of coexpressed proteins and clusters of tumors. We delineated protein clusters associated with the estrogen receptor and with proliferation. Tumor clusters correlated with several histoclinical features of samples, including 5-year metastasis-free survival (MFS), and with the recently proposed pathophysiologic taxonomy of disease. The supervised method identified a set of 21 proteins whose combined expression significantly correlated to MFS in a learning set of 368 patients (P < 0.0001) and in a validation set of 184 patients (P < 0.0001). Among the 552 patients, the 5-year MFS was 90% for patients classified in the “good-prognosis class” and 61% for those classified in the “poor-prognosis class” (P < 0.0001). This difference remained significant when the molecular grouping was applied according to lymph node or estrogen receptor status, as well as the type of adjuvant systemic therapy. In multivariate analysis, the 21-protein set was the strongest independent predictor of clinical outcome. These results show that protein expression profiling may be a clinically useful approach to assess breast cancer heterogeneity and prognosis in stage I, II, or III disease.