In Gram-positive bacteria, such as lactic acid bacteria, general glycosylation systems have not been documented so far. The aim of this work was to characterize in detail the glycosylation of the S-layer protein of Lactobacillus kefiri CIDCA 83111. A reductive β-elimination treatment followed by anion exchange high performance liquid chromatography analysis was useful to characterize the O-glycosidic structures. MALDI-TOF mass spectrometry analysis confirmed the presence of oligosaccharides bearing from 5 to 8 glucose units carrying galacturonic acid. Further nanoHPLC-ESI analysis of the glycopeptides showed two O-glycosylated peptides: the peptide sequence SSASSASSA already identified as a signature glycosylation motif in L. buchneri, substituted on average with eight glucose residues and decorated with galacturonic acid and another O-glycosylated site on peptide 471–476, with a Glc5–8GalA2 structure. As ten characteristic sequons (Asn-X-Ser/Thr) are present in the S-layer amino acid sequence, we performed a PNGase F digestion to release N-linked oligosaccharides. Anion exchange chromatography analysis showed mainly short N-linked chains. NanoHPLC-ESI in the positive and negative ion modes were useful to determine two different peptides substituted with short N-glycan structures. To our knowledge, this is the first description of the structure of N-glycans in S-layer glycoproteins from Lactobacillus species.