The Drosophila Ash1 protein is a trithorax-group (trxG) regulator that antagonizes Polycomb repression at HOX genes. Ash1 di-methylates lysine 36 in histone H3 (H3K36me2) but how this activity is controlled and at which genes it functions is not well understood. We show that Ash1 protein purified from Drosophila exists in a complex with MRG15 and Caf1 that we named AMC. In Drosophila and human AMC, MRG15 binds a conserved FxLP motif near the Ash1 SET domain and stimulates H3K36 di-methylation on nucleosomes. Drosophila MRG15-null and ash1 catalytic mutants show remarkably specific trxG phenotypes: stochastic loss of HOX gene expression and homeotic transformations in adults. In mutants lacking AMC, H3K36me2 bulk levels appear undiminished but H3K36me2 is reduced in the chromatin of HOX and other AMC-regulated genes. AMC therefore appears to act on top of the H3K36me2/me3 landscape generated by the major H3K36 methyltransferases NSD and Set2. Our analyses suggest that H3K36 di-methylation at HOX genes is the crucial physiological function of AMC and the mechanism by which the complex antagonizes Polycomb repression at these genes.