Protein concentrations evolve under greater evolutionary constraint than mRNA levels. Translation efficiency of mRNA represents the chief determinant of basal protein concentrations. This raises a fundamental question of how mRNA and protein levels are coordinated in dynamic systems responding to physiological stimuli. This report examines the contributions of mRNA abundance and translation efficiency to protein output in cells responding to oxygen stimulus. We show that changes in translation efficiencies, and not mRNA levels, represent the major mechanism governing cellular responses to [O2] perturbations. Two distinct cap-dependent protein synthesis machineries select mRNAs for translation: the normoxic eIF4F and the hypoxic eIF4FH. O2-dependent remodeling of translation efficiencies enables cells to produce adaptive translatomes from preexisting mRNA pools. Differences in mRNA expression observed under different [O2] are likely neutral, given that they occur during evolution. We propose that mRNAs contain translation efficiency determinants for their triage by the translation apparatus on [O2] stimulus.