The bacterium Yersinia enterocolitica serotype O:3 is targeted by two distinct agents, the bacteriophage φR1-37 and the bacteriocin-like enterocoliticin (a tailocin), which both utilize the lipopolysaccharide (LPS) outer core (OC) hexasaccharide as their primary host receptor. In order to understand this convergent recognition mechanism, we first characterized the enterocoliticin system, reporting the complete sequence of its large, biosynthesis gene cluster. Most of the 42 predicted gene products were functionally annotated by homology to known gene products. We then focused on identifying the receptor binding proteins (RBPs) responsible for host attachment of both agents in order to elucidate a possible shared mechanism of binding. For phage φR1-37, the receptor binding complex was identified as the inseparable Gp298 tail fiber protein and its Gp297 trimerization chaperone, confirming its function as the RBP. Based on sequence identity with Gp298, the Orf39 gene product of the enterocoliticin cluster was predicted to be its corresponding RBP. An analytical comparison of the predicted RBPs revealed a highly conserved homologous region spanning 80–85 amino acid residues, which presents the only structural explanation for their identical receptor specificity. To resolve the binding mechanism, we generated high-confidence trimeric structural models for the Gp298 and Orf39 proteins using AlphaFold3-multimer. These models validated the high structural similarity of the RBP domains, despite global dissimilarity of the complete trimeric structures. Further docking simulations with a pentasaccharide ligand (generated by CarbBuilder) provided suggestive molecular models for the protein-carbohydrate interactions within the OC region. Intriguingly, a database search using the identified binding site motif revealed their wide and diverse presence in various phage tail proteins, suggesting that this motif is a specialized, common structure for carbohydrate recognition. This work identifies a conserved, novel sugar binding motif to be the molecular basis of host recognition for these key anti-Yersinia biologics.