In Drosophila, X chromosome dosage compensation requires the male-specific lethal (MSL) complex, which associates with actively transcribed genes on the single male X chromosome to upregulate transcription approximately 2-fold. We found that on the male X chromosome, or when MSL complex is ectopically localized to an autosome, histone H3K36 trimethylation (H3K36me3) is a strong predictor of MSL binding. We isolated mutants lacking Set2, the H3K36me3 methyltransferase, and found that Set2 is an essential gene in both sexes of Drosophila. In set2 mutant males, MSL complex maintains X specificity but exhibits reduced binding to target genes. Furthermore, recombinant MSL3 protein preferentially binds nucleosomes marked by H3K36me3 in vitro. Our results support a model in which MSL complex uses high-affinity sites to initially recognize the X chromosome and then associates with many of its targets through sequence-independent features of transcribed genes.