In this study, we investigated the anti-proliferative effect of polysaccharides from Salicornia herbacea on HT-29 human colon cancer cells. Crude polysaccharides from S. herbacea (CS) were prepared by extraction with hot steam water, and fine polysaccharides from S. herbacea (PS) were obtained through further size exclusion chromatography. The anti-proliferative effect of CS and PS were measured using the MTS assay, apoptosis analysis, cell cycle analysis, and RT-PCR. HT-29 cells were treated with CS or PS at different dosages (0.5, 1, 2, 4 mg $ml^{-1}$) for 24 or 48 h. CS and PS inhibited proliferation and stimulated apoptosis of cells in a dose-dependent manner. Flow cytometric analysis after Annexin V-FITC and PI staining revealed that treatment with CS or PS increased total apoptotic death of cells to 24.99% or 91.59%, respectively, in comparison with the control (13.51 %). PS increased early apoptotic death substantially - up to 12 times more than the control. Treatment with CS or PS resulted in a concentration-dependent increase of the G2/M cell population of the cell cycle as determined by flow cytometry. G2/M arrest was induced significantly with the highest concentration (4 mg $ml^{-1}$) of PS. RT-PCR was performed to study the correlation between G2/M arrest and transcription of cell cycle control genes. The anti-proliferative activity of CS and PS was accompanied by inhibition of cyclin B1, and Cdc 2 mRNA. Moreover, both CS and PS induced expression of the p53 tumor suppressor gene and the Cdk inhibitor p21. These results suggest that polysaccharides from S. herbacea have anti-cancer activity in human colon cancer cells.