The existence of a trade-off between the biomass yield and growth rate of cells has been used to explain aerobic fermentation in cancer cells (Warburg effect), yeast cells (Crabtree effect) and in bacteria such as E. coli. This trade-off relies on the assumption that even though fermentation pathways produce 5-10 times less ATP per glucose, respiration requires so much more resources and is therefore inefficient when carbon is not limiting. Is this trade-off a universal constraint imposed by thermodynamics, or a coincidental feature of the specific enzyme kinetic parameters that evolved in these organisms? To answer this question we developed a new method called Enzyme-Flux Cost Minimization (EFCM) to model the costs of both respiration and fermentation (along with ~1000 other flux combinations called elementary flux modes). We find that the trade-off in E. coli is not universal and depends strongly on the availability of oxygen. This framework successfully predicts in vivo enzyme concentrations, and has applications in metabolic engineering where similar candidate pathways can be compared not just by their yields, but also by their costs.