Potential mobility of restriction-modification systems has been suggested by evolutionary/bioinformatic analysis of prokaryotic genomes. Here we demonstrate in vivo movement of a restriction-modification system within a genome under a laboratory condition. After blocking replication of a temperature-sensitive plasmid carrying a PaeR7I restriction-modification system in Escherichia coli cells, the plasmid was found integrated into the chromosome of the surviving cells. Sequence analysis revealed that, in the majority of products, the restriction-modification system was linked to chromosomal insertion sequences (ISs). Three types of products were: (I) apparent co-integration of the plasmid and the chromosome at a chromosomal IS1 or IS5 copy (24/28 analyzed); (II) de novo insertion of IS1 with the entire plasmid except for a 1-3 bp terminal deletion (2/28); and (III) reciprocal crossing-over between the plasmid and the chromosome involving 1-3 bp of sequence identity (2/28). An R-negative mutation apparently decreased the efficiency of successful integration by two orders of magnitude. Reconstruction experiments demonstrated that the restriction-dependence was mainly due to selection against cells without proper integration: their growth was inhibited by the restriction enzyme action. These results demonstrate collaboration of a mobile element and a restriction-modification system for successful joint migration. This collaboration may have promoted the spread and, therefore, the long-term persistence of these complexes and restriction-modification systems in a wide range of prokaryotes.