Therapeutic combinations to alter immunosuppressive, solid tumor microenvironments (TME), such as in breast cancer, are essential to improve responses to immune checkpoint inhibitors (ICI). Entinostat, an oral histone deacetylase inhibitor, has been shown to improve responses to ICIs in various tumor models with immunosuppressive TMEs. The precise and comprehensive alterations to the TME induced by entinostat remain unknown. Here, we employed single-cell RNA sequencing on HER2-overexpressing breast tumors from mice treated with entinostat and ICIs to fully characterize changes across multiple cell types within the TME. This analysis demonstrates that treatment with entinostat induced a shift from a protumor to an antitumor TME signature, characterized predominantly by changes in myeloid cells. We confirmed myeloid-derived suppressor cells (MDSC) within entinostat-treated tumors associated with a less suppressive granulocytic (G)-MDSC phenotype and exhibited altered suppressive signaling that involved the NFκB and STAT3 pathways. In addition to MDSCs, tumor-associated macrophages were epigenetically reprogrammed from a protumor M2-like phenotype toward an antitumor M1-like phenotype, which may be contributing to a more sensitized TME. Overall, our in-depth analysis suggests that entinostat-induced changes on multiple myeloid cell types reduce immunosuppression and increase antitumor responses, which, in turn, improve sensitivity to ICIs. Sensitization of the TME by entinostat could ultimately broaden the population of patients with breast cancer who could benefit from ICIs.