Natural polysaccharides (PSs) have shown inhibitory effects on differentiated cancer cells (DCCs), but their activity against cancer stem cells (CSCs) remains poorly understood. Here, we report that PSs from wheat cell cultures (WCCPSs) inhibit the proliferation of both DCCs and CSCs derived from HCT-116 colorectal cancer cells. Among them, NA and DC fractions showed the strongest anti-CSC activity. NA, rich in xylose, was effective at lower concentrations, while DC, enriched in xylose and galacturonic acid (GalUA), exhibited higher potency, with a lower IC and preferential activity against CSCs at higher doses. WCCPSs reduced β-catenin levels, and some fractions also downregulated Ep-CAM, CD44, and c-Myc. Notably, DC increased caspase-3 without inducing cytochrome C and caspase-8 overexpression, suggesting a mechanism promoting CSC differentiation rather than apoptosis. Correlation analysis linked xylose content to reduced c-Myc expression, and GalUA levels to increased caspase-3. These results suggest that WCCPS bioactivity may be related to their monosaccharide composition. Overall, our findings support the potential of wheat-derived PSs as CSC-targeting agents that suppress self-renewal and promote differentiation, offering a promising approach to reduce tumor aggressiveness and recurrence.