LSD1 is a recently identified human lysine (K)-specific histone demethylase. LSD1 is associated with HDAC1/2; CoREST, a SANT domain-containing corepressor; and BHC80, a PHD domain-containing protein, among others. We show that CoREST endows LSD1 with the ability to demethylate nucleosomal substrates and that it protects LSD1 from proteasomal degradation in vivo. We find hyperacetylated nucleosomes less susceptible to CoREST/LSD1-mediated demethylation, suggesting that hypoacetylated nucleosomes may be the preferred physiological substrates. This raises the possibility that histone deacetylases and LSD1 may collaborate to generate a repressive chromatin environment. Consistent with this model, TSA treatment results in derepression of LSD1 target genes. While CoREST positively regulates LSD1 function, BHC80 inhibits CoREST/LSD1-mediated demethylation in vitro and may therefore confer negative regulation. Taken together, these findings suggest that LSD1-mediated histone demethylation is regulated dynamically in vivo. This is expected to have profound effects on gene expression under both physiological and pathological conditions.