The inability of the yeast Saccharomyces cerevisiae to ferment xylose effectively under anaerobic conditions is a major barrier to economical production of lignocellulosic biofuels. Although genetic approaches have enabled engineering of S. cerevisiae to convert xylose efficiently into ethanol in defined lab medium, few strains are able to ferment xylose from lignocellulosic hydrolysates in the absence of oxygen. This limited xylose conversion is believed to result from small molecules generated during biomass pretreatment and hydrolysis, which induce cellular stress and impair metabolism. Here, we describe the development of a xylose-fermenting S. cerevisiae strain with tolerance to a range of pretreated and hydrolyzed lignocellulose, including Ammonia Fiber Expansion (AFEX)-pretreated corn stover hydrolysate (ACSH). We genetically engineered a hydrolysate-resistant yeast strain with bacterial xylose isomerase and then applied two separate stages of aerobic and anaerobic directed evolution. The emergent S. cerevisiae strain rapidly converted xylose from lab medium and ACSH to ethanol under strict anaerobic conditions. Metabolomic, genetic and biochemical analyses suggested that a missense mutation in GRE3, which was acquired during the anaerobic evolution, contributed toward improved xylose conversion by reducing intracellular production of xylitol, an inhibitor of xylose isomerase. These results validate our combinatorial approach, which utilized phenotypic strain selection, rational engineering and directed evolution for the generation of a robust S. cerevisiae strain with the ability to ferment xylose anaerobically from ACSH.