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-α1,4-d-glucuronic acid linkage that caps the side chains of complex AGPs. The reaction product generated by the lyase, Δ4,5-unsaturated uronic acid, is removed from AGP by a glycoside hydrolase located in family GH105, producing the final product 4-deoxy-β-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 (α/α)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 β-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.