Aberrant protein acetylation is strongly linked to tumourigenesis, and modulating acetylation through targeting histone deacetylase (HDAC) with small molecule inhibitors has been the focus of clinical trials. However, clinical success on solid tumours, like colorectal cancer (CRC), has been limited, in part because the cancer-relevant mechanisms through which HDAC inhibitors act remain largely unknown. Here, we have explored, at the genome-wide expression level, the effects of a novel HDAC inhibitor CXD101. In human CRC cell lines, a diverse set of differentially expressed genes were up- and down-regulated upon CXD101 treatment. Functional profiling of the expression data highlighted immune-relevant concepts related to antigen processing (AP) and natural killer (NK) cell mediated cytotoxicity. Similar profiles were apparent when gene expression was investigated in murine colon26 CRC cells treated with CXD101. Significantly, these changes were also apparent in syngeneic colon26 tumours growing in vivo. The ability of CXD101 to affect immune-relevant gene expression coincided with changes in the tumour micro-environment (TME), especially in the sub-groups of CD4 and CD8 tumour-infiltrating T lymphocytes. The altered TME reflected enhanced anti-tumour activity when CXD101 was combined with immune checkpoint inhibitors (ICIs), such as anti-PD1 and anti-CTLA4. The ability of CXD101 to re-instate immune-relevant gene expression in the TME and act together with ICIs provides a powerful rationale for exploring the combination therapy in human cancers.