Novel probiotic strains that can ferment prebiotics are important for functional foods. The utilization of prebiotics is strain specific, so we screened 86 Lactobacillus strains and compared them to Bifidobacterium breve 2141 for the ability to grow and produce SCFA when 1% inulin or fructo-oligosaccharides (FOS) were provided as the carbon source in batch fermentations. When grown anaerobically at 32 °C, ten Lactobacillus strains grew on both prebiotic substrates (OD600 ≥ 1.2); while Lactobacillus coryniformis subsp. torquens B4390 grew only in the presence of inulin. When the growth temperature was increased to 37 °C to simulate the human body temperature, four of these strains were no longer able to grow on either prebiotic. Additionally, L. casei strains 4646 and B441, and L. helveticus strains B1842 and B1929 did not require anaerobic conditions for growth on both prebiotics. Short-chain fatty acid analysis was performed on cell-free supernatants. The concentration of lactic acid produced by the ten Lactobacillus strains in the presence of prebiotics ranged from 73–205 mM. L. helveticus B1929 produced the highest concentration of acetic acid ~19 mM, while L. paraplantarum B23115 and L. paracasei ssp. paracasei B4564 produced the highest concentrations of propionic (1.8–4.0 mM) and butyric (0.9 and 1.1 mM) acids from prebiotic fermentation. L. mali B4563, L. paraplantarum B23115 and L. paracasei ssp. paracasei B4564 were identified as butyrate producers for the first time. These strains hold potential as synbiotics with FOS or inulin in the development of functional foods, including infant formula.