Ethylene is a small hydrocarbon gas widely used in the chemical industry. Annual worldwide production currently exceeds 150 million tons, producing considerable amounts of CO2 contributing to climate change. The need for a sustainable alternative is therefore imperative. Ethylene is natively produced by several different microorganisms, including Pseudomonas syringae pv. phaseolicola via a process catalyzed by the ethylene forming enzyme (EFE), subsequent heterologous expression of EFE has led to ethylene production in non-native bacterial hosts including E. coli and cyanobacteria. However, solubility of EFE and substrate availability remain rate limiting steps in biological ethylene production. We employed a combination of genome scale metabolic modelling, continuous fermentation, and protein evolution to enable the accelerated development of a high efficiency ethylene producing E. coli strain, yielding a 49-fold increase in production, the most significant improvement reported to date. Furthermore, we have clearly demonstrated that this increased yield resulted from metabolic adaptations that were uniquely linked to the EFE enzyme (WT vs mutant). Our findings provide a novel solution to deregulate metabolic bottlenecks in key pathways, which can be readily applied to address other engineering challenges.