Anti-phage systems of the BREX (BacteRiophage EXclusion) superfamily rely on site-specific epigenetic DNA methylation to discriminate between the host and invading DNA. We demonstrate that in Type I BREX systems, defense and methylation require BREX site DNA binding by the BrxX (PglX) methyltransferase employing S-adenosyl methionine as a cofactor. We determined 2.2-Å cryoEM structure of Escherichia coli BrxX bound to target dsDNA revealing molecular details of BREX DNA recognition. Structure-guided engineering of BrxX expands its DNA specificity and dramatically enhances phage defense. We show that BrxX alone does not methylate DNA, and BREX activity requires an assembly of a supramolecular BrxBCXZ immune complex. Finally, we present a cryoEM structure of BrxX bound to a phage-encoded inhibitor Ocr that sequesters BrxX in an inactive dimeric form. We propose that BrxX-mediated foreign DNA sensing is a necessary first step in activation of BREX defense.