The MspJI modification-dependent restriction endonuclease recognizes 5-methylcytosine or 5-hydroxymethylcytosine in the context of CNN(G/A) and cleaves both strands at fixed distances (N12/N16) away from the modified cytosine at the 3′-side. We determined the crystal structure of MspJI of Mycobacterium sp. JLS at 2.05-Å resolution. Each protein monomer harbors two domains: an N-terminal DNA-binding domain and a C-terminal endonuclease. The N-terminal domain is structurally similar to that of the eukaryotic SET and RING-associated domain, which is known to bind to a hemi-methylated CpG dinucleotide. Four protein monomers are found in the crystallographic asymmetric unit. Analytical gel-filtration and ultracentrifugation measurements confirm that the protein exists as a tetramer in solution. Two monomers form a back-to-back dimer mediated by their C-terminal endonuclease domains. Two back-to-back dimers interact to generate a tetramer with two double-stranded DNA cleavage modules. Each cleavage module contains two active sites facing each other, enabling double-strand DNA cuts. Biochemical, mutagenesis and structural characterization suggest three different monomers of the tetramer may be involved respectively in binding the modified cytosine, making the first proximal N12 cleavage in the same strand and then the second distal N16 cleavage in the opposite strand. Both cleavage events require binding of at least a second recognition site either in cis or in trans.