Prokaryotes evolved numerous systems that defend against predation by bacteriophages. In addition to well-known restriction-modification and CRISPR-Cas immunity systems, many poorly characterized systems exist. One class of such systems, named BREX, consists of a putative phosphatase, a methyltransferase and four other proteins. A Bacillus cereus BREX system provides resistance to several unrelated phages and leads to modification of specific motif in host DNA. Here, we study the action of BREX system from a natural Escherichia coli isolate. We show that while it makes cells resistant to phage λ infection, induction of λ prophage from cells carrying BREX leads to production of viruses that overcome the defense. The induced phage DNA contains a methylated adenine residue in a specific motif. The same modification is found in the genome of BREX-carrying cells. The results establish, for the first time, that immunity to BREX system defense is provided by an epigenetic modification.