The Myc oncoprotein is a potent inducer of cell growth, cell cycle progression, and apoptosis. While many direct Myc target genes have been identified, the molecular determinants of Myc's transcriptional specificity remain elusive. We have carried out a genetic screen in Drosophila and identified the Trithorax group protein Little imaginal discs (Lid) as a regulator of dMyc-induced cell growth. Lid binds to dMyc and is required for dMyc-induced expression of the growth regulatory gene Nop60B. The mammalian Lid orthologs, Rbp-2 (JARID1A) and Plu-1 (JARID1B), also bind to c-Myc, indicating that Lid-Myc function is conserved. We demonstrate that Lid is a JmjC-dependent trimethyl H3K4 demethylase in vivo and that this enzymatic activity is negatively regulated by dMyc, which binds to Lid's JmjC domain. Because Myc binding is associated with high levels of trimethylated H3K4, we propose that the Lid-dMyc complex facilitates Myc binding to, or maintenance of, this chromatin context.