The prognosis of patients with metastatic breast cancer remains poor, and thus novel therapeutic approaches are needed. Capecitabine, which is commonly used for metastatic breast cancer in different settings, is an inactive prodrug that takes advantage of elevated levels of thymidine phosphorylase (TP), a key enzyme that is required for its conversion to 5-fluororacil, in tumors. We demonstrated that histone deacetylase inhibitors (HDACi), including low anticonvulsant dosage of VPA, induced the dose- and time-dependent up-regulation of TP transcript and protein expression in breast cancer cells, but not in the non-tumorigenic breast MCF-10A cell line. Through the use of siRNA or isoform-specific HDACi, we demonstrated that HDAC3 is the main isoform whose inhibition is involved in the modulation of TP. The combined treatment with capecitabine and HDACi, including valproic acid (VPA), resulted in synergistic/additive antiproliferative and pro-apoptotic effects in breast cancer cells but not in TP-knockout cells, both in vitro and in vivo, highlighting the crucial role of TP in the synergism observed. Overall, this study suggests that the combination of HDACi (e.g., VPA) and capecitabine is an innovative antitumor strategy that warrants further clinical evaluation for the treatment of metastatic breast cancer.