The transcriptional corepressor complex CoREST is one of seven histone deacetylase complexes that regulate the genome through controlling chromatin acetylation. The CoREST complex is unique in containing both histone demethylase and deacetylase enzymes, LSD1 and HDAC1, held together by the RCOR1 scaffold protein. To date, it has been assumed that the enzymes function independently within the complex. Now, we report the assembly of the ternary complex. Using both structural and functional studies, we show that the activity of the two enzymes is closely coupled and that the complex can exist in at least two distinct states with different kinetics. Electron microscopy of the complex reveals a bi-lobed structure with LSD1 and HDAC1 enzymes at opposite ends of the complex. The structure of CoREST in complex with a nucleosome reveals a mode of chromatin engagement that contrasts with previous models.