Most Eukaryotes recognise flagellin as a signature of bacterial invasion. In contrast to animals, plants do not recognise flagellin proteins, but conserved peptides released from flagellin (Felix et al., 1999). However, these peptides (e.g. flg22) are folded and buried deeply inside the flagellin polymer and would need to be released before they can interact with cell surface receptors, such as FLS2 (Fliegman & Felix, 2016). Here we discovered that the hydrolytic pathway releasing the flagellin elicitor in plants is initiated by a host-secreted beta-galactosidase (BGAL), which removes the terminal modified viosamine (mVio) from the O-glycan that cloaks the flagellin polymer. BGAL contributes to flagellin-dependent immunity but only against bacterial Pseudomonas syringae strains that carry mVio. Signatures of arms races at this new level of antagonistic interactions are that BGAL is suppressed during infection by a heat stable metabolite secreted by bacteria, and that other P. syringae strains carry BGAL-insensitive O-glycans.