ABSTRACT The Gram-positive bacterium Lactococcus lactis is used for the production of cheeses and other fermented dairy products. Accidental infection of L. lactis cells by virulent lactococcal tailed phages is one of the major risks of fermentation failures in industrial dairy factories. Lactococcal phage 1358 possesses a host range limited to a few L. lactis strains and strong genomic similarities to Listeria phages. We report here the X-ray structures of phage 1358 receptor binding protein (RBP) in complex with monosaccharides. Each monomer of its trimeric RBP is formed of two domains: a “shoulder” domain linking the RBP to the rest of the phage and a jelly roll fold “head/host recognition” domain. This domain harbors a saccharide binding crevice located in the middle of a monomer. Crystal structures identified two sites at the RBP surface, ∼8 Å from each other, one accommodating a GlcNAc monosaccharide and the other accommodating a GlcNAc or a glucose 1-phosphate (Glc1P) monosaccharide. GlcNAc and GlcNAc1P are components of the polysaccharide pellicle that we identified at the cell surface of L. lactis SMQ-388, the host of phage 1358. We therefore modeled a galactofuranose (Gal f ) sugar bridging the two GlcNAc saccharides, suggesting that the trisaccharidic motif GlcNAc-Gal f -GlcNAc (or Glc1P) might be common to receptors of genetically distinct lactococcal phages p2, TP091-1, and 1358. Strain specificity might therefore be elicited by steric clashes induced by the remaining components of the pellicle hexasaccharide. Taken together, these results provide a first insight into the molecular mechanism of host receptor recognition by lactococcal phages. IMPORTANCE Siphophages infecting the Gram-positive bacterium Lactococcus lactis are sources of milk fermentation failures in the dairy industry. We report here the structure of the pellicle polysaccharide from L. lactis SMQ-388, the specific host strain of phage 1358. We determined the X-ray structures of the lytic lactococcal phage 1358 receptor binding protein (RBP) in complex with monosaccharides. The positions and nature of monosaccharides bound to the RBP are in agreement with the pellicle structure and suggest a general binding mode of lactococcal phages to their pellicle saccharidic receptor.