The human gut microbiota utilizes complex carbohydrates as major nutrients. The requirement for efficient glycan degrading systems exerts a major selection pressure on this microbial community. Thus, we propose that this microbial ecosystem represents a substantial resource for discovering novel carbohydrate active enzymes. To test this hypothesis we screened the potential enzymatic functions of hypothetical proteins encoded by genes of Bacteroides thetaiotaomicron that were up-regulated by arabinogalactan proteins or AGPs. Although AGPs are ubiquitous in plants, there is a paucity of information on their detailed structure, the function of these glycans in planta, and the mechanisms by which they are depolymerized in microbial ecosystems. Here we have discovered a new polysaccharide lyase family that is specific for the L-rhamnose-alpha 1,4-D-glucuronic acid linkage that caps the side chains of complex AGPs. The reaction product generated by the lyase, Delta 4,5-unsaturated uronic acid, is removed from AGP by a glycoside hydrolase located in family GH105, producing the final product 4-deoxy-beta-L-threo-hex-4-enepyranosyl- uronic acid. The crystal structure of a member of the novel lyase family revealed a catalytic domain that displays an (alpha/alpha)(6) barrel-fold. In the center of the barrel is a deep pocket, which, based on mutagenesis data and amino acid conservation, comprises the active site of the lyase. A tyrosine is the proposed catalytic base in the beta-elimination reaction. This study illustrates how highly complex glycans can be used as a scaffold to discover new enzyme families within microbial ecosystems where carbohydrate metabolism is a major evolutionary driver.