Lentinula edodes (shiitake or Xianggu) is one of the most widely consumed edible fungi, valued for its appealing flavor and notable nutritional and health-promoting properties. Polysaccharides extracted from L. edodes (LePS) have been reported to exhibit diverse bioactivities, including immunomodulatory, antioxidant, and antitumor effects. In this study, a β-glucan-rich polysaccharide fraction, LePS40, was isolated from the aqueous extract of L. edodes by precipitation with 40% ethanol. LePS40 showed strong resistance to digestive enzymes and gastric acid under simulated human gastrointestinal conditions, but was highly fermentable during in vitro fermentation with human fecal microbiota. Fermentation-induced degradation of LePS40 appeared to selectively cleave glucosidic linkages, as indicated by a marked decrease in the molar ratio of glucose. Compared with the prebiotic reference fructooligosaccharides (FOS), LePS40 produced significantly higher levels of butyric and propionic acids, but a lower level of acetic acid. In addition, LePS40 increased the relative abundance of several beneficial bacterial populations while reducing taxa potentially associated with fatty liver disease and colorectal cancer. Furthermore, fermentation products of LePS40 exhibited a protective effect on intestinal barrier function against inflammation-induced damage in a Caco-2/RAW264.7 co-culture model. These findings suggest that LePS40 has potential as a functional ingredient for improving gut health through modulation of the gut microbiota and its metabolites.