A polysaccharide was isolated from Flammulina velutipes (FVP) using ultrasonic-assisted extraction, and then further purified by DEAE cellulose-52 chromatography and Sephadex G-100 size-exclusion chromatography to afford FVP-1 and FVP-2. Structural characteristics of FVP-1 and FVP-2 (including molecular weight, monosaccharides composition, sulfate and uronic acid contents, triple helical structures, ultraviolet spectrum, and infrared spectrum) were investigated, and their anti-proliferation activities against human gastric cancer BGC-823 cells and lung cancer A549 cells were researched in vitro. Results suggested that both FVP-1 and FVP-2 could significantly suppress the proliferation of BGC-823 cells in a concentration-dependent manner. The highest inhibitory rates were 78% for FVP-1 and 95% for FVP-2 at the concentration of 200μg/ml, respectively. This high anti-proliferation activity was inferred to be owing to the structural characterizations of polysaccharide, and the recognition of biological system for the triple helical structures of polysaccharides.