Histone deacetylase (HDAC) inhibitors are a promising class of anticancer agents for the treatment of solid and hematological malignancies. The precise mechanism by which HDAC inhibitors mediate their effects on tumor cell growth, differentiation, and/or apoptosis is the subject of intense research. Previously we described a family of multiprotein complexes that contain histone deacetylase 1/2 (HDAC1/2) and the histone demethylase BHC110 (LSD1). Here we show that HDAC inhibitors diminish histone H3 lysine 4 (H3K4) demethylation by BHC110 in vitro. In vivo analysis revealed an increased H3K4 methylation concomitant with inhibition of nucleosomal deacetylation by HDAC inhibitors. Reconstitution of recombinant complexes revealed a functional connection between HDAC1 and BHC110 only when nucleosomal substrates were used. Importantly, while the enzymatic activity of BHC110 is required to achieve optimal deacetylation in vitro, in vivo analysis following ectopic expression of an enzymatically dead mutant of BHC110 (K661A) confirmed the functional cross talk between the demethylase and deacetylase enzymes. Our studies not only reveal an intimate link between the histone demethylase and deacetylase enzymes but also identify histone demethylation as a secondary target of HDAC inhibitors.