This study systematically isolated a high-molecular-weight polysaccharide (HHEP; 9.14 × 103 kDa) from Hericium erinaceus, consisting predominantly of glucose (59.16% ± 0.09%), galactose (26.29% ± 0.59%), and mannose (5.69% ± 0.58%). Through an in vitro simulated gastrointestinal digestion and colonic fermentation model, the HHEP demonstrated remarkable resistance to digestive enzymes and gastric acid hydrolysis. However, it was effectively utilized by gut microbiota during fermentation. Detailed monitoring indicated an initial cleavage of glycosidic bonds, accompanied by a pH decrease and the formation of high-molecular-weight fragments, followed by progressive microbial degradation. Compared with inulin, HHEP selectively enriched beneficial genera, notably, Prevotella and Akkermansia. Furthermore, fermentation supernatants from early fermentation stages─when larger fragments prevailed─induced immune responses in RAW 264.7 macrophages. These results demonstrate the digestive stability and prebiotic potential of HHEP, highlighting its role as a gut-microbiota-targeting ingredient with structure-dependent immunomodulatory properties.