Several Lactobacillus plantarum strains are marketed as probiotics for their potential health benefits. Prebiotics, e.g., galacto-oligosaccharides (GOS), have the potential to selectively stimulate the growth of L. plantarum probiotic strains based on their phenotypic diversity in carbohydrate utilization, and thereby enhance their health promoting effects in the host in a strain-specific manner. Previously, we have shown that GOS variably promotes the strain-specific growth of L. plantarum. In this study we investigated this variation by molecular analysis of GOS utilization by L. plantarum. HPAEC-PAD analysis revealed two distinct GOS utilization phenotypes in L. plantarum. Linking these phenotypes to the strain-specific genotypes led to the identification of a lac operon encoding a β-galactosidase (lacA), a permease (lacS), and a divergently oriented regulator (lacR), that are predicted to be involved in the utilization of higher degree of polymerization (DP) constituents present in GOS (specifically DP of 3–4). Mutation of lacA and lacS in L. plantarum NC8 resulted in reduced growth on GOS, and HPAEC analysis confirmed the role of these genes in the import and utilization of higher-DP GOS constituents. Overall, the results enable the design of highly-selective synbiotic combinations of L. plantarum strain-specific probiotics and specific GOS-prebiotic fractions.