It is of interest to discover new fermentable carbohydrate sources that function as prebiotics. This study evaluated the hydrolytic digestibility, fermentative capacity, and microbiota modulating properties of Temulose molasses, four hydrolyzed fractions of Temulose molasses, short-chain fructooligosaccharides (scFOS), and a yeast cell wall preparation (Safmannan). These substrates resisted in vitro hydrolytic digestion. Each substrate was fermented in vitro using dog fecal inoculum, and fermentation characteristics were quantified at 0 and 12 h. All Temulose molasses substrates decreased pH by at least 0.64 unit and resulted in greater (P < 0.05) butyrate and total short-chain fatty acid (SCFA) production compared to scFOS and Safmannan. Temulose molasses substrates resulted in higher (P < 0.01) or equal Bifidobacterium spp. concentrations compared to scFOS. Temulose molasses substrate and its fractions demonstrated prebiotic characteristics as indicated by low hydrolytic digestibility, high fermentability, and enhanced growth of microbiota considered to be beneficial to health.