Bacterial exopolysaccharides (EPS) display extensive structural diversity arising from variation in monosaccharide composition, glycosidic linkages, and non-carbohydrate modifications. However, the enzymes responsible for degrading many EPS structures remain unknown, reflecting the limited coverage of current carbohydrate-active enzyme (CAZyme) families. Here, we investigated the microbial degradation of EPSLp, a high-molecular-mass glycosaminogalactan from Lactiplantibacillus pentosus KW1 containing the uncommon GalNAcβ1→2(4,6-O-R-pyruvyl)Gal motif. Enrichment cultivation with EPSLp as the sole carbon source led to the isolation of Luteolibacter sp. VK1, a novel strain capable of utilizing this biopolymer. Size-exclusion chromatography and MALDI-TOF mass spectrometry showed that VK1 depolymerizes EPSLp into defined oligosaccharides, consistent with endo-acting cleavage followed by further processing. By combining genomics, AlphaFold-based structural annotation and comparative proteomics, we identified candidate CAZymes potentially involved in EPSLp catabolism. Notably, a secreted GH123 protein and a distantly related GH123-like protein were strongly associated with EPSLp-dependent growth, suggesting that this enzyme family, or related structural homologues, may contribute to extracellular EPSLp depolymerization. Together, these findings reveal a candidate pathway for degradation of a structurally complex, pyruvylated bacterial glycan and provide a foundation for biochemical characterization of novel EPS-active enzymes.