The constant arms race between bacteria and their parasites has resulted in a large diversity of bacterial defenses, with many bacteria carrying multiple systems. Here, we report the discovery of a phylogenetically widespread defense system, coined methylation-associated defense system (MADS), which is distributed across gram-positive and gram-negative bacteria. MADS interacts with a CRISPR-Cas system in its native host to provide robust and durable resistance against phages. While phages can acquire epigenetic-mediated resistance against MADS, co-existence of MADS and a CRISPR-Cas system limits escape emergence. MADS comprises eight genes with predicted nuclease, ATPase, kinase, and methyltransferase domains, most of which are essential for either self/non-self discrimination, DNA restriction, or both. The complex genetic architecture of MADS and MADS-like systems, relative to other prokaryotic defenses, points toward highly elaborate mechanisms of sensing infections, defense activation, and/or interference.