The gene MLL (encoding the protein mixed-lineage leukemia) is the target of chromosomal translocations that cause leukemias with poor prognosis. All leukemogenic MLL fusion proteins retain the CXXC domain, which binds to nonmethylated CpG DNA sites. We present the solution structure of the MLL CXXC domain in complex with DNA, showing how the CXXC domain distinguishes nonmethylated from methylated CpG DNA. On the basis of the structure, we generated point mutations that disrupt DNA binding. Introduction of these mutations into the MLL-AF9 fusion protein resulted in increased DNA methylation of specific CpG nucleotides in Hoxa9, increased H3K9 methylation, decreased expression of Hoxa9-locus transcripts, loss of immortalization potential, and inability to induce leukemia in mice. These results establish that DNA binding by the CXXC domain and protection against DNA methylation is essential for MLL fusion leukemia. They also provide support for viewing this interaction as a potential target for therapeutic intervention.