BACKGROUND: The complexity of plant cell walls creates many challenges for microbial decomposition. Clostridium phytofermentans, an anaerobic bacterium isolated from forest soil, directly breaks down and utilizes many plant cell wall carbohydrates. The objective of this research is to understand constraints on rates of plant decomposition by Clostridium phytofermentans and identify molecular mechanisms that may overcome these limitations. RESULTS: Experimental evolution via repeated serial transfers during exponential growth was used to select for C. phytofermentans genotypes that grow more rapidly on cellobiose, cellulose and xylan. To identify the underlying mutations an average of 13,600,000 paired-end reads were generated per population resulting in approximately 300 fold coverage of each site in the genome. Mutations with allele frequencies of 5% or greater could be identified with statistical confidence. Many mutations are in carbohydrate-related genes including the promoter regions of glycoside hydrolases and amino acid substitutions in ABC transport proteins involved in carbohydrate uptake, signal transduction sensors that detect specific carbohydrates, proteins that affect the export of extracellular enzymes, and regulators of unknown specificity. Structural modeling of the ABC transporter complex proteins suggests that mutations in these genes may alter the recognition of carbohydrates by substrate-binding proteins and communication between the intercellular face of the transmembrane and the ATPase binding proteins. CONCLUSIONS: Experimental evolution was effective in identifying molecular constraints on the rate of hemicellulose and cellulose fermentation and selected for putative gain of function mutations that do not typically appear in traditional molecular genetic screens. The results reveal new strategies for evolving and engineering microorganisms for faster growth on plant carbohydrates.