Probiotics are microbes that promote health when consumed in sufficient amounts. They are present in many fermented foods or can be provided directly as supplements. Probiotics utilize non-digestible prebiotic oligosaccharides for growth in the intestinal tract, contributing to a healthy microbiome. The oligosaccharides favored by probiotics are species-dependent, as shown by the selective utilization of substrates in mixed sugar solutions such as crude fructo-oligosaccharides (FOS). Enzymatically produced crude FOS preparations contain abundant monosaccharide byproducts, residual sucrose, and FOS varying in chain length. Here we investigated the metabolic profiles of four probiotic bacteria during the batch fermentation of crude FOS under controlled conditions. We found that rapidly utilized most of the monosaccharides but little sucrose or FOS. We therefore tested the feasibility of a microbial fed-batch fermentation process for the purification of FOS from crude preparations, which increased the purity of FOS from 59.2 to 82.5% with a final concentration of 140 g·l. We also tested cell immobilization in alginate beads as a means to remove monosaccharides from crude FOS. This encapsulation concept establishes the basis for new synbiotic formulations that combine probiotic microbes and prebiotic oligosaccharides.