Russula vinosa Lindblad (R. vinosa Lindblad) is a nutrient-rich wild edible fungus, abundant in carbohydrates. In this study, two polysaccharides (Russula polysaccharides extracted from 1% KOH (RP-1) and Russula polysaccharides extracted from 5% KOH (RP-5)) were extracted from Russula fruit bodies using KOH-graded extraction technology. The molecular weights of RP-1 and RP-5 were 187 000 and 97 300 u, respectively. Their glycosyl compositions (galactose:glucose:xylose:mannose, i.e., Gal:Glu:Xyl:Man) were 0.27:1.00:0.01:0.16 for RP-1 and 0.12:1.00:0.03:0.19 for RP-5. Nuclear magnetic resonance (NMR) analysis revealed that the main structural component of RP-1 was →3,6)-β-D-Glup-(1→, with a →6)-β-D-Glup-(1→ residue linked at sites 1 and 6, and a →3)-β-D-Glup-(1→ residue linked at sites 3. The RP-5 shared this structure with an additional →4)-β-D-Manp-(1→ residue attached to the →3)-β-D-Glup-(1→. Phagocytosis assay demonstrated that RP-5, with a lower molecular weight, lower galactose content, and higher xylose and mannose content, enhanced RAW 264.7 cell phagocytic activity by 121.04%, outperforming RP-1, which showed a 42.15% increase at the same concentration of 600 μg/mL. Furthermore, both RP-1 and RP-5 reduced the release of inflammatory factors and induced the nuclear translocation of the nuclear transcription factor-κB (NF-κB) pathway in RAW 264.7 cells. This study provided insights into the structural characteristics and immunomodulatory properties of Russula polysaccharides, offering potential for further applications in bioactive compound development.