Breast cancer is a very heterogeneous disease, encompassing several intrinsic subtypes with various morphological and molecular features, natural history and response to therapy. Currently, molecular targeted therapies are available for estrogen receptor (ER)- and human epidermal growth factor receptor 2 (Her2)-positive breast tumors. However, a significant proportion of primary breast cancers are negative for ER, progesterone receptor (PgR), and Her2, comprising the triple negative breast cancer (TNBC) group. Women with TNBC have a poor prognosis due to the aggressive nature of these tumors and current lack of suitable targeted therapies. As a consequence, the identification of novel relevant protein targets for this group of patients is of great importance. Using a systematic 2D gel-based proteomic profiling strategy, applied to the analysis of fresh TNBC tissue biopsies, in combination with a three-tier orthogonal technology (2D PAGE/silver staining coupled with MS, 2D Western blotting, and immunohistochemistry) approach, we aimed to identify targetable protein markers that were present in a significant fraction of samples and that could define therapy-amenable sub-groups of TNBCs. We present here our results, including a large cumulative database of proteins based on the analysis of 78 TNBCs, and the identification and validation of one specific protein, Mage-A4, which was expressed in a significant fraction of TNBC and Her2-positive/ER negative lesions. The high level expression of Mage-A4 in the tumors studied allowed the detection of the protein in the tumor interstitial fluids as well as in sera. The existence of immunotherapeutics approaches specifically targeting this protein, or MAGE-A protein family members, and the fact that we were able to detect its presence in serum suggest novel management options for TNBC and Her2 positive/ER negative patients bearing Mage-A4 positive tumors.