Human lysine-specific demethylase (LSD1) is a chromatin-modifying enzyme that specifically removes methyl groups from mono- and dimethylated Lys4 of histone H3 (H3-K4). We used a combination of in vivo and in vitro experiments to characterize the substrate specificity and recognition by LSD1. Biochemical assays on histone peptides show that essentially all epigenetic modifications on the 21 N-terminal amino acids of histone H3 cause a significant reduction in enzymatic activity. Replacement of Lys4 with Arg greatly enhances binding affinity, and a histone peptide incorporating this mutation has a strong inhibitory power. Conversely, a peptide bearing a trimethylated Lys4 is only a weak inhibitor of the enzyme. Rapid kinetics measurements evidence that the enzyme is efficiently reoxidized by molecular oxygen with a second-order rate constant of 9.6×10^3 M-1 s-1, and that the presence of the reaction product does not greatly influence the rate of flavin reoxidation. In vivo experiments provide a correlation between the in vitro inhibitory properties of the tested peptides and their ability of affecting endogenous LSD1 activity. Our results show that epigenetic modifications on histone H3 need to be removed before Lys4 demethylation can efficiently occur. The complex formed by LSD1 with histone deacetylases 1/2 may function as a “double-blade razor” that first eliminates the acetyl groups from acetylated Lys residues and then removes the methyl group from Lys4. We suggest that after H3-K4 demethylation, LSD1 recruits the forthcoming chromatin remodelers leading to the introduction of gene repression marks.