Posttranslational modifications of histone N-terminal tails impact chromatin structure and gene transcription. While the extent of histone acetylation is determined by both acetyltransferases and deacetylases, it has been unclear whether histone methylation is also regulated by enzymes with opposing activities. Here, we provide evidence that LSD1 (KIAA0601), a nuclear homolog of amine oxidases, functions as a histone demethylase and transcriptional corepressor. LSD1 specifically demethylates histone H3 lysine 4, which is linked to active transcription. Lysine demethylation occurs via an oxidation reaction that generates formaldehyde. Importantly, RNAi inhibition of LSD1 causes an increase in H3 lysine 4 methylation and concomitant derepression of target genes, suggesting that LSD1 represses transcription via histone demethylation. The results thus identify a histone demethylase conserved from S. pombe to human and reveal dynamic regulation of histone methylation by both histone methylases and demethylases.