Histone methylation regulates diverse chromatin-templated processes, including transcription. Many transcriptional corepressor complexes contain lysine-specific demethylase 1 (LSD1) and CoREST that collaborate to demethylate mono- and dimethylated H3-K4 of nucleosomes. Here, we report the crystal structure of the LSD1-CoREST complex. LSD1-CoREST forms an elongated structure with a long stalk connecting the catalytic domain of LSD1 and the CoREST SANT2 domain. LSD1 recognizes a large segment of the H3 tail through a deep, negatively charged pocket at the active site and possibly a shallow groove on its surface. CoREST SANT2 interacts with DNA. Disruption of the SANT2-DNA interaction diminishes CoREST-dependent demethylation of nucleosomes by LSD1. The shape and dimension of LSD1-CoREST suggest its bivalent binding to nucleosomes, allowing efficient H3-K4 demethylation. This spatially separated, multivalent nucleosome binding mode may apply to other chromatin-modifying enzymes that generally contain multiple nucleosome binding modules.