Many organisms expand the information content of their genome through enzymatic methylation of cytosine residues. Here we report the 2.8 Angstrom crystal structure of a bacterial DNA (cytosine-5)-methyltransferase (DCMtase), M. HaeIII, bound covalently to DNA. In this complex, the substrate cytosine is extruded from the DNA helix and inserted into the active site of the enzyme, as has been observed for another DCMtase, M. HhaI. The DNA is bound in a cleft between the two domains of the protein and is distorted from the characteristic B-form conformation at its recognition sequence. A comparison of structures shows a variation in the mode of DNA recognition: M. HaeIII differs from M. HhaI in that the remaining bases in its recognition sequence undergo an extensive rearrangement in their pairing. In this process, the bases are unstacked, and a gap 8 Angstrom long opens in the DNA.