Epigenetic indexing of chromatin domains by histone lysine methylation requires the balanced coordination of methyltransferase and demethylase activities. Here, we show that SU(VAR)3-3, the Drosophila homolog of the human LSD1 amine oxidase, demethylates H3K4me2 and H3K4me1 and facilitates subsequent H3K9 methylation by SU(VAR)3-9. Su(var)3-3 mutations suppress heterochromatic gene silencing, display elevated levels of H3K4me2, and prevent extension of H3K9me2 at pericentric heterochromatin. SU(VAR)3-3 colocalizes with H3K4me2 in interband regions and is abundant during embryogenesis and in syncytial blastoderm, where it appears concentrated at prospective heterochromatin during cycle 14. In embryos of Su(var)3-3/+ females, H3K4me2 accumulates in primordial germ cells, and the deregulated expansion of H3K4me2 antagonizes heterochromatic H3K9me2 in blastoderm cells. Our data indicate an early developmental function for the SU(VAR)3-3 demethylase in controlling euchromatic and heterochromatic domains and reveal a hierarchy in which SU(VAR)3-3-mediated removal of activating histone marks is a prerequisite for subsequent heterochromatin formation by H3K9 methylation.