This study aimed at providing a route towards the production of a novel exopolysaccharide (EPS) from fermented bamboo shoot-isolated Lactobacillus fermentum. A lactic acid bacteria strain, with high EPS production ability, was isolated from fermented bamboo shoots. This strain, R-49757, was identified in the BCCM/LMG Bacteria Collection, Ghent University, Belgium by the phenylalanyl-tRNA synthetase gene sequencing method, and it was named Lb. fermentum MC3. The molecular mass of the EPS measured via gel permeation chromatography was found to be 9.85 × 104 Da. Moreover, the monosaccharide composition in the EPS was analyzed by gas chromatography–mass spectrometry. Consequently, the EPS was discovered to be a heteropolysaccharide with the appearance of two main sugars—D-glucose and D-mannose—in the backbone. The results of one-dimensional (1D) and two-dimensional (2D) nuclear magnetic resonance spectroscopy analyses prove the repeating unit of this polysaccharide to be [→6)-β-D-Glcp-(1→3)-β-D-Manp-(1→6)-β-D-Glcp-(1→]n, which appears to be a new EPS. The obtained results open up an avenue for the production of novel EPSs for biomedical applications.