A novel histone methyltransferase, termed Set9, was isolated from human cells. Set9 contains a SET domain, but lacks the pre- and post-SET domains. Set9 methylates specifically lysine 4 (K4) of histone H3 (H3-K4) and potentiates transcription activation. The histone H3 tail interacts specifically with the histone deacetylase NuRD complex. Methylation of histone H3-K4 by Set9 precludes the association of NuRD with the H3 tail. Moreover, methylation of H3-K4 impairs Suv39h1-mediated methylation at K9 of H3 (H3-K9). The interplay between the Set9 and Suv39h1 histone methyltransferases is specific, as the methylation of H3-K9 by the histone methyltransferase G9a was not affected by Set9 methylation of H3-K4. Our studies suggest that Set9-mediated methylation of H3-K4 functions in transcription activation by competing with histone deacetylases and by precluding H3-K9 methylation by Suv39h1. Our results suggest that the methylation of histone tails can have distinct effects on transcription, depending on its chromosomal location, the combination of posttranslational modifications, and the enzyme (or protein complex) involved in the particular modification.