Recognizing the methylation status of specific DNA sequences is central to the function of many systems in eukaryotes and prokaryotes. Restriction-modification systems have to distinguish between 'self' and 'non-self' DNA and depend on the inability of restriction endonucleases to cleave their DNA substrates when the DNA is appropriately methylated. These endonucleases thus provide a model system for studying the recognition of DNA methylation by proteins. We have characterized the interaction of R.PVU:II with DNA containing the physiologically relevant N4-methylcytosine modification. R.PVU:II binds (N4m)C-modified DNA and cleaves it very slowly. Methylated strands in hemimethylated duplexes were cleaved at a higher rate than in fully methylated duplexes, in parallel with a higher binding affinity for hemimethylated DNA. The co-crystal structures of R.PVU:II-DNA, together with a mutagenesis study, have implicated specific amino acids in recognition of the methylatable base; one of these is His84. We report that replacing His84 with Ala reduced the rate of cleavage of unmodified DNA but, in contrast, slightly increased the cleavage of (N4m)C-modified DNA.