Biofuels produced by microbes, including Saccharomyces cerevisiae, have promise as a non-petroleum based energy system. Biofuel production from agricultural waste, such as corn stover, would provide an important advance because it would not compete with food sources. However, corn stover contains high concentrations of xylose, which S. cerevisiae cannot naturally ferment, for reasons that are not understood. This defect renders nearly a third of the potential carbon in corn stover biomass unutilized. To address this, an engineered S. cerevisiae strain containing bacterial xylose isomerase was subjected to directed evolution for over 200 generations. Strain Y127 was evolved from a stress-tolerant wild yeast strain (Y22-3) for aerobic xylose fermentation; strain Y128 was further evolved from Y127 to ferment xylose anaerobically. Whole-genome sequencing identified responsible mutations in the evolved strains, but the physiological effect of these mutations remains unclear. To better understand the physiology of these strains, we performed genome-scale analyses to study differences in gene expression (RNA-seq), protein levels (label-free quantitative mass-spec proteomics), and phosphorylation abundance (mass-spec phosphoproteomics) on the parental strain and the two evolved strains, in the presence of glucose or xylose and under aerobic or anaerobic growth conditions. Remarkably, comparison of the mRNA and protein changes revealed a disconnect between mRNA and protein abundance in the unevolved strain growing anaerobically on xylose, and a defect in mounting the hypoxic response when cells are grown anaerobically on xylose. Over-expression of AZF1 significantly improved anaerobic xylose fermentation in the evolved Y128 strain, but only during anaerobic growth on xylose. Comparative analysis across the multi-omic datasets implicates downstream targets of Azf1 and upstream regulatory pathways that enable anaerobic xylose fermentation. These results present important new insights into how anaerobic xylose fermentation can be engineered in yeast and reveal new connections between sugar and oxygen responses.