Immunotherapy has demonstrated clinical efficacy in subsets of patients with solid carcinomas. Multimodal therapies using agents that can affect different arms of the immune system and/or tumor microenvironment (TME) might increase clinical responses. We demonstrate that entinostat, a class I histone deacetylase inhibitor, enhances the antitumor efficacy of the IL15 superagonist N-803 plus vaccine in 4T1 triple-negative breast and MC38-CEA colon murine carcinoma models. A comprehensive immune and gene-expression analysis was performed in the periphery and/or TME of MC38-CEA tumor-bearing mice. Although N-803 plus vaccine induced peripheral CD8 T-cell activation and cytokine production, there was no reduction in tumor burden and poor tumor infiltration of CD8 T cells with minimal levels of granzyme B. For the first time, we demonstrate that the addition of entinostat to N-803 plus vaccine promoted significant tumor control, correlating with increased expression of genes associated with tumor inflammation, enhanced infiltration of activated CD8 T cells with maximal granzyme B, T-cell responses to multiple tumor-associated antigens, increased serum IFNγ, reduction of regulatory T cells in the TME, and decreased expression of the checkpoint V-domain Ig suppressor of T-cell activation (VISTA) on multiple immune subsets. Collectively, these data demonstrate that the synergistic combination of entinostat, N-803, and vaccine elicits potent antitumor activity by generating a more inflamed TME. These findings thus form the rationale for the use of this combination of agents for patients harboring poorly or noninflamed solid carcinomas.