Probiotics, prebiotics, and combinations thereof, that is, synbiotics, are known to exert beneficial health effects in humans; however interactions between pro- and prebiotics remain poorly understood at the molecular level. The present study describes changes in abundance of different proteins of the probiotic bacterium Lactobacillus acidophilus NCFM (NCFM) when grown on the potential prebiotic cellobiose as compared to glucose. Cytosolic cell extract proteomes after harvest at late exponential phase of NCFM grown on cellobiose or glucose were analyzed by two dimensional difference gel electrophoresis (2D-DIGE) in the acidic (pH 4-7) and the alkaline (pH 6-11) regions showing a total of 136 spots to change in abundance. Proteins were identified by MS or MS/MS from 81 of these spots representing 49 unique proteins and either increasing 1.5-13.9-fold or decreasing 1.5-7.8-fold in relative abundance. Many of these proteins were associated with energy metabolism, including the cellobiose related glycoside hydrolases phospho-β-glucosidase (LBA0881) and phospho-β-galactosidase II (LBA0726). The data provide insight into the utilization of the candidate prebiotic cellobiose by the probiotic bacterium NCFM. Several of the upregulated or downregulated identified proteins associated with utilization of cellobiose indicate the presence of carbon catabolite repression and regulation of enzymes involved in carbohydrate metabolism.