An Astragalus residue was reutilized through solid-state fermentation by Paecilomyces sinensis, which is a member of Ophiocordyceps sinensis (Berk.) Sacc. In this research, the polysaccharide from the product of solid-state fermentation primarily was studied. First, HPLC, FT-IR, and GC were applied to study the preliminary characterization of a polysaccharide (APP-II) from the solid-state fermentation product Astragalus residue and Paecilomyces sinensis. Results indicated that APP-II is a-pyran polysaccharide with an average molecular weight of 670 kD that is composed of rhamnose, arabinose, xylose, mannose, glucose, and galactose with a molar ratio of 4.0 : 4.2 : 2.0 : 41.4 : 22.5 : 25.9. Second, an immunostimulatory activity of APP-I and APP-II was detected. Results suggested that APP-I and APP-II could promote RAW264.7 cell proliferation. APP-I was used to detect the immunostimulatory activity of APP-II in vivo. The results indicated that APP-I can promote growth of immune organs, stimulate splenocyte proliferation, and enhance NK activity; this indicated that APP-II had immunostimulatory activity in vivo. All the results indicated that APP-II is a novel polysaccharide with immunostimulatory activity.