The human intestine hosts a complex bacterial community that plays a major role in nutrition and in maintaining human health. A functional metagenomic approach was used to explore the prebiotic breakdown potential of human gut bacteria, including non-cultivated ones. Two metagenomic libraries, constructed from ileum mucosa and fecal microbiota, were screened for hydrolytic activities on the prebiotic carbohydrates inulin, fructo-oligosaccharides, xylo-oligosaccharides, galacto-oligosaccharides and lactulose. The DNA inserts of 17 clones, selected from the 167 hits that were identified, were pyrosequenced in-depth, yielding in total 407, 420 bp of metagenomic DNA. From these sequences, we discovered novel prebiotic degradation pathways containing carbohydrate transporters and hydrolysing enzymes, for which we provided the first experimental proof of function. Twenty of these proteins are encoded by genes that are also present in the gut metagenome of at least 100 subjects, whatever are their ages or their geographical origin. The sequence taxonomic assignment indicated that still unknown bacteria, for which neither culture conditions nor genome sequence are available, possess the enzymatic machinery to hydrolyse the prebiotic carbohydrates tested. The results expand the vision on how prebiotics are metabolized along the intestine, and open new perspectives for the design of functional foods.