Breast cancer is the second leading cause of cancer death for women in the United States. Of the different subtypes, estrogen receptor-negative (ER(-)) tumors, which are ErbB2+ or triple-negative, carry a relatively poor prognosis. In this study, we used system-wide analysis of breast cancer proteomes to identify proteins that are associated with the progression of ER(-) tumors. Our two-step approach included an initial deep analysis of cultured cells that were obtained from tumors of defined breast cancer stages, followed by a validation set using human breast tumors. Using high-resolution mass spectrometry and quantification by Stable Isotope Labeling with Amino Acids in Cell Culture (SILAC), we identified 8,750 proteins and quantified 7,800 of them. A stage-specific signature was extracted and validated by mass spectrometry and immunohistochemistry on tissue microarrays. Overall, the proteomics signature reflected both a global loss of tissue architecture and a number of metabolic changes in the transformed cells. Proteomic analysis also identified high levels of IDH2 and CRABP2 and low levels of SEC14L2 to be prognostic markers for overall breast cancer survival. Together, our findings suggest that global proteomic analysis provides information about the protein changes specific to ER(-) breast tumor progression as well as important prognostic information.