Adjuvant chemo- and/or radiotherapy is applied in a majority of patients treated for early stage breast cancer, although only a small percentage of these individuals are at high risk of metastasis or recurrence. Hence, knowledge of the biomarkers associated with the risk of disease progression might facilitate the planning of an optimal therapy and protect many patients from the toxicity of unnecessary treatment. In this study, we characterized the serum proteome of patients diagnosed with early-stage breast cancer, exhibiting either no evidence of disease five years after the end of therapy or suffering from metastasis, relapse or a second cancer during the corresponding follow-up. Samples collected before treatment and one year after the end of therapy, when no clinical symptoms of a treatment failure was evidenced, were analyzed using two classical proteomics approaches: LC-MS/MS and 2D-PAGE. A total of 42 proteins with relative quantities that were significantly different between pre- and post-treatment samples were identified in either group of patients; however, the observed changes were more frequent in the treatment-failure group. Among the posttreatment samples, 30 proteins were upregulated, and 10 proteins were downregulated, while 11 proteins were upregulated, and eight proteins were downregulated in the control group. Moreover, several proteins exhibited different patterns of changes in both groups of patients. For example, haptoglobin expression increased in the treatment-failure group but decreased in the control group (this pattern of changes was confirmed using an immunoassay). Notably, proteins affected in posttreatment samples in either group of patients could be associated with different molecular and cellular functions, including angiogenesis, blood coagulation and wound healing in the treatment-failure group and cell adhesion and cell death in the control group.