The restriction systems McrA and McrB of Escherichia coli K-12 are known to attack DNA containing modified cytosine. In strains lacking both activities, however, we observed that DNA methylated at CG dinucleotides (as is mammalian DNA) was still significantly restricted. We show that this substantial barrier to the acceptance of 5-methylcytosine-containing DNA is attributable to a hitherto unknown activity of the Mrr restriction system. Strikingly, the multiple systems used by this gut inhabitant to determine the fate of invading DNA will all limit genetic exchange with its mammalian host(s), reinforcing the idea that one role of DNA methylation is to serve as a "molecular passport" (E. A. Raleigh, R. Trimarchi, and H. Revel, Genetics 122:279-296, 1989).