Histone methylation regulates diverse chromatin-templated processes, including transcription. The recent discovery of the first histone lysine-specific demethylase (LSD1) has changed the long-held view that histone methylation is a permanent epigenetic mark. LSD1 is a flavin adenine dinucleotide (FAD)-dependent amine oxidase that demethylates histone H3 Lys4 (H3-K4). However, the mechanism by which LSD1 achieves its substrate specificity is unclear. We report the crystal structure of human LSD1 with a propargylamine-derivatized H3 peptide covalently tethered to FAD. H3 adopts three consecutive gamma-turns, enabling an ideal side chain spacing that places its N terminus into an anionic pocket and positions methyl-Lys4 near FAD for catalysis. The LSD1 active site cannot productively accommodate more than three residues on the N-terminal side of the methyllysine, explaining its H3-K4 specificity. The unusual backbone conformation of LSD1-bound H3 suggests a strategy for designing potent LSD1 inhibitors with therapeutic potential.