Gentio-oligosaccharides (GnOS) were synthesized by the acceptor reaction of dextransucrase from Leuconostoc mesenteroides NRRL B-1426 with gentiobiose and sucrose. GnOS were purified by gel permeation chromatography using a Bio-Gel P-2 column and identified by mass spectrometry. The purified GnOS (degree of polymerization ≥3) were investigated for their in vitro prebiotic and cytotoxic activity. GnOS exhibited a significantly lower degree of digestibility of 18.1% by simulated human gastric juice (pH 1.0) and 7.1% by human α-amylase (pH 7.0) after 6 h, whereas inulin, a standard prebiotic, showed 39.7% and 12.8% of digestibility, respectively. The prebiotic score showed that GnOS significantly supported the growth of probiotics such as Bifidobacterium infantis and Lactobacillus acidophilus and was comparable to that of inulin. The selective inhibitory effect of GnOS on human colon carcinoma (HT-29) cells revealed its potential as an anti-cancer agent that can serve as a functional food additive for the benefit of human health.