Saccharomyces cerevisiae is unique among yeasts in its ability to grow rapidly in the complete absence of oxygen. S. cerevisiae is therefore an ideal eukaryotic model to study physiological adaptation to anaerobiosis. Recent transcriptome analyses have identified hundreds of genes that are transcriptionally regulated by oxygen availability but the relevance of this cellular response has not been systematically investigated at the key control level of the proteome. Therefore, the proteomic response of S. cerevisiae to anaerobiosis was investigated using metabolic stable-isotope labelling in aerobic and anaerobic glucose-limited chemostat cultures, followed by relative quantification of protein expression. Using independent replicate cultures and stringent statistical filtering, a robust dataset of 474 quantified proteins was generated, of which 249 showed differential expression levels. While some of these changes were consistent with previous transcriptome studies, many of the responses of S. cerevisiae to oxygen availability were, to our knowledge, previously unreported. Comparison of transcriptomes and proteomes from identical cultivations yielded strong evidence for post-transcriptional regulation of key cellular processes, including glycolysis, amino-acyl-tRNA synthesis, purine nucleotide synthesis and amino acid biosynthesis. The use of chemostat cultures provided well-controlled and reproducible culture conditions, which are essential for generating robust datasets at different cellular information levels. Integration of transcriptome and proteome data led to new insights into the physiology of anaerobically growing yeast that would not have been apparent from differential analyses at either the mRNA or protein level alone, thus illustrating the power of multi-level studies in yeast systems biology.