A novel polysaccharide FVPB2 was purified from fruiting bodies of Flammulina velutipes. Its structure was elucidated by monosaccharide composition and methylation analyses, UV-Visible and FTIR spectroscopy as well as NMR. FVPB2 was a homogeneous heteropolysaccharide (molecular weight ~ 1.50 × 104 Da) containing D-galactose, D-mannose, L-fucose, and D-glucose at molar ratio of 1.9:1.2:1:2.5. In vitro immunomodulatory studies showed FVPB2 induced proliferation of mouse spleen lymphocytes in a dose-dependent manner. The levels of IgM and IgG, secreted by B cells, increased after FVPB2 treatment. So FVPB2 has potential to be a new important immunomodulatory nutraceutical.