Capparis spionosa L. is a traditional medicinal plant in China and central Asia. In this study, an experiment was designed to investigate the optimization of the extraction of anti-tumor polysaccharides from the fruit of Capparis spionosa L. (CSPS) by response surface methodology (RSM). Four independent variables (extraction temperature, extraction time, ratio of water to sample and extraction cycles) were explored. Meanwhile, the in vivo anti-tumor activity of CSPS was investigated. The results showed that the experimental data could be fitted to a second-order polynomial equation using multiple regression analysis. The optimum extraction conditions were as follows: extraction temperature 92 °C, extraction time 140 min, ratio of water to sample 26 mL/g, and three extraction cycle. Under these conditions, the yield of polysaccharides reached 13.01%, which was comparable to the predicted yield (12.94%, p > 0.05). This indicated that the model was adequate for the extraction process. Additionally, CSPS could prolong the survival time of H22 bearing mice in vivo. The anti-tumor activities of CSPS were dose-dependent.