This study employs a combination of protein structural similarity and gene co-occurrence analyses to identify anti-phage and counter-defense systems in viral proteins and metagenome-assembled genomes. By predicting structures for approximately 300,000 proteins and performing large-scale pairwise comparisons with known anti-CRISPR (Acr) and anti-phage proteins, the researchers identify a *Bacteroidota* phage Acr protein that inhibits Cas2a and an *Akkermansia muciniphila* anti-phage defense protein, named BxaP. BxaP is found in loci encoding Bacteriophage Exclusion (BREX) and restriction-modification (RM) defense systems but confers immunity independently. The work highlights the advantages of combining protein structural features and gene co-localization information in studying host-phage interactions, expanding the repertoire of defense and counter-defense systems and providing insights into the ongoing evolutionary arms race between phages and their hosts.This study employs a combination of protein structural similarity and gene co-occurrence analyses to identify anti-phage and counter-defense systems in viral proteins and metagenome-assembled genomes. By predicting structures for approximately 300,000 proteins and performing large-scale pairwise comparisons with known anti-CRISPR (Acr) and anti-phage proteins, the researchers identify a *Bacteroidota* phage Acr protein that inhibits Cas2a and an *Akkermansia muciniphila* anti-phage defense protein, named BxaP. BxaP is found in loci encoding Bacteriophage Exclusion (BREX) and restriction-modification (RM) defense systems but confers immunity independently. The work highlights the advantages of combining protein structural features and gene co-localization information in studying host-phage interactions, expanding the repertoire of defense and counter-defense systems and providing insights into the ongoing evolutionary arms race between phages and their hosts.