Natural gums are consumer safe heteropolysaccharides with industrial applications. These soluble dietary fibres, due to their inherent structural complexity, makes them a suitable candidate for prebiotic studies. Our study evaluated the prebiotic potential of four natural gums and their partial hydrolysates on the growth of six lactic acid bacterial strains, including four Lactobacillus species (Lactobacillus plantarum, L. brevis, L. rhamnosus, and L. bifermentans) and two strains of Lactococcus lactis subsp. lactis. Guar gum (Galactomannan), Acacia gum (Arabinogalactan), tamarind gum (glucan), and flaxseed gum (xylan) were targeted for prebiotic evaluation. CFU counts, optical density, pH, and BCA assay (reducing sugar estimation) revealed that not all natural gums are equally effective. Partial depolymerisation has significantly boosted the growth of specific strains, suggesting that the complexity of the native form limits its utilisation. In silico studies indicated the link between species-specific substrate utilisation and glycosyl hydrolases production and also variations in the number of isozymes present across the species. Quantitative real-time data validated the differential expression of the targeted glycosidase when grown on partially hydrolysed substrate compared to the native gums. Our findings highlight the biochemical and molecular basis for substrate preference and provide insights into potential combinations for formulating synbiotics.