Genome-scale metabolic reconstructions capture the known metabolic capabilities of organisms and their analysis have provided many insights into complex biochemical networks. However, this approach relies on a database of known biochemical reactions and hence may fail to take into account unique novel metabolic reactions. Even for well-characterized model organisms like E. coli, new reactions remain to be discovered. Starting from the known biochemistry of E. coli metabolism, we investigated how many more reactions could be evolved and if these reactions could give extra potential to this organism for industrial application in the production of fuels and chemicals. We utilized the BNICE (Biochemical Network Integrated Computational Explorer) methodology which applies known biotransformation rules to generate a “super” network which captures all the possible reactions given a set of E. coli core metabolites and known biotransformation rules in E. coli. This super network is found to capture all the known E. coli reactions as well as novel pathways that can serve as potential novel biosynthesis pathways to valuable chemicals. In order to identify the role of these novel reactions in E. coli metabolic network, we embedded them within the genome scale model of E. coli and performed a thermodynamics flux balance analysis (TFBA) to investigate the feasibility of the novel pathways in the context of the genome scale model. By performing a Flux Variability Analysis (FVA), subject to thermodynamic constraints, the reliable sets of reactions that increase the yield through biomass were identified. To further investigate the feasibility of the novel proposed reactions, we used the BridgIT computational framework for the identification of candidate gene sequences. BridgIT has a database of all the known biochemical reactions and it makes associations between novel predicted reactions and known reactions by using a chemical similarity metrics and it links the novel reactions with known genes in genomes and organisms.