Background: Saccharomyces cerevisiae, a key organism used for the manufacture of renewable fuels and chemicals, has been engineered to utilize non-native sugars derived from plant cell walls, such as cellobiose and xylose. However, the rates and efficiencies of these non-native sugar fermentations pale in comparison with those of glucose. Systems biology methods, used to understand biological networks, hold promise for rational microbial strain development in metabolic engineering. Here, we present a systematic strategy for optimizing non-native sugar fermentation by recombinant S. cerevisiae, using cellobiose as a model. Results: Differences in gene expression between cellobiose and glucose metabolism revealed by RNA deep sequencing indicated that cellobiose metabolism induces mitochondrial activation and reduces amino acid biosynthesis under fermentation conditions. Furthermore, glucose-sensing and signaling pathways and their target genes, including the cAMP-dependent protein kinase A pathway controlling the majority of glucose-induced changes, the Snf3-Rgt2-Rgt1 pathway regulating hexose transport, and the Snf1-Mig1 glucose repression pathway, were at most only partially activated under cellobiose conditions. To separate correlations from causative effects, the expression levels of 19 transcription factors perturbed under cellobiose conditions were modulated, and the three strongest promoters under cellobiose conditions were applied to fine-tune expression of the heterologous cellobiose-utilizing pathway. Of the changes in these 19 transcription factors, only overexpression of SUT1 or deletion of HAP4 consistently improved cellobiose fermentation. SUT1 overexpression and HAP4 deletion were not synergistic, suggesting that SUT1 and HAP4 may regulate overlapping genes important for improved cellobiose fermentation. Transcription factor modulation coupled with rational tuning of the cellobiose consumption pathway significantly improved cellobiose fermentation. Conclusions: We used systems-level input to reveal the regulatory mechanisms underlying suboptimal metabolism of the non-glucose sugar cellobiose. By identifying key transcription factors that cause suboptimal cellobiose fermentation in engineered S. cerevisiae, and by fine-tuning the expression of a heterologous cellobiose consumption pathway, we were able to greatly improve cellobiose fermentation by engineered S. cerevisiae. Our results demonstrate a powerful strategy for applying systems biology methods to rapidly identify metabolic engineering targets and overcome bottlenecks in performance of engineered strains.