The Gram-positive bacterium Oenococcus oeni is a major player in wine malolactic fermentation. In O. oeni, cell wall polysaccharides are considered putative receptors for bacteriophages, virus predators that lead to fermentation failures. In this study, we have developed an efficient stepwise extraction protocol to extract polysaccharides from the cell wall of O. oeni IOEBS277, which were analyzed by methylation, 1D, 2D-NMR spectroscopy, and MALDI-QIT-TOF mass spectrometry. The chemical structures of the two major purified polysaccharides were elucidated. The first one is a heteropolysaccharide with repeating units consisting of a branched hexasaccharide and one glycerol residue, linked by phosphodiester bonds. The second one consists of a →6)-β-Galf-(1→ galactofuranan chain partially substituted on the C-2 hydroxyl with β-Glcp. HR-MAS NMR analysis of intact O. oeni cells indicated that both polysaccharides are exposed to the bacterial surface.