(1) Background: Immunosuppression is a key barrier to effective anti-cancer therapies, particularly in triple-negative breast cancer (TNBC), an aggressive and difficult to treat form of breast cancer. We investigated here whether the combination of doxorubicin, a standard chemotherapy in TNBC with glyceryltrinitrate (GTN), a nitric oxide (NO) donor, could overcome chemotherapy resistance and highlight the mechanisms involved in a mouse model of TNBC. (2) Methods: Balb/C-bearing subcutaneous 4T1 (TNBC) tumors were treated with doxorubicin (8 mg/Kg) and GTN (5 mg/kg) and monitored for tumor growth and tumor-infiltrating immune cells. The effect of treatments on MDSCs reprogramming was investigated ex vivo and in vitro. (3) Results: GTN improved the anti-tumor efficacy of doxorubicin in TNBC tumors. This combination increases the intra-tumor recruitment and activation of CD8 lymphocytes and dampens the immunosuppressive function of PMN-MDSCs PD-L1 . Mechanistically, in PMN-MDSC, the doxorubicin/GTN combination reduced STAT5 phosphorylation, while GTN +/- doxorubicin induced a ROS-dependent cleavage of STAT5 associated with a decrease in FATP2. (4) Conclusion: We have identified a new combination enhancing the immune-mediated anticancer therapy in a TNBC mouse model through the reprograming of PMN-MDSCs towards a less immunosuppressive phenotype. These findings prompt the testing of GTN combined with chemotherapies as an adjuvant in TNBC patients experiencing treatment failure.