Methylation of Lys residues on histone proteins is a well known and extensively characterized epigenetic mark. The recent discovery of lysine-specific demethylase 1 (LSD1) demonstrated that lysine methylation can be dynamically controlled. Among the histone demethylases so far identified, LSD1 has the unique feature of functioning through a flavin-dependent amine oxidation reaction. Data base analysis reveals that mammalian genomes contain a gene (AOF1, for amine-oxidase flavin-containing domain 1) that is homologous to the LSD1-coding gene. Here, we demonstrate that the protein encoded by AOF1 represents a second mammalian flavin-dependent histone demethylase, named LSD2. The new demethylase is strictly specific for mono- and dimethylated Lys4 of histone H3, recognizes a long stretch of the H3 N-terminal tail, senses the presence of additional epigenetic marks on the histone substrate, and is covalently inhibited by tranylcypromine. As opposed to LSD1, LSD2 does not form a biochemically stable complex with the C-terminal domain of the corepressor protein CoREST. Furthermore, LSD2 contains a CW-type zinc finger motif with potential zinc-binding sites that are not present in LSD1. We conclude that mammalian LSD2 represents a new flavin-dependent H3-Lys4 demethylase that features substrate specificity properties highly similar to those of LSD1 but is very likely to be part of chromatin-remodeling complexes that are distinct from those involving LSD1.