Cofactors, such as NAD(H) and NADP(H), play important roles in energy transfer within the cells by providing the necessary redox carriers for a myriad of metabolic reactions, both anabolic and catabolic. Thus, it is crucial to establish the overall cellular redox balance for achieving the desired cellular physiology. Of several methods to manipulate the intracellular cofactor regeneration rates, altering the cofactor specificity of a particular enzyme is a promising one. However, the identification of relevant enzyme targets for such cofactor specificity engineering (CSE) is often very difficult and labor intensive. Therefore, it is necessary to develop more systematic approaches to find the cofactor engineering targets for strain improvement. Presented herein is a novel mathematical framework, cofactor modification analysis (CMA), developed based on the well-established constraints-based flux analysis, for the systematic identification of suitable CSE targets while exploring the global metabolic effects. The CMA algorithm was applied to E. coli using its genome-scale metabolic model, iJO1366, thereby identifying the growth-coupled cofactor engineering targets for overproducing four of its native products: acetate, formate, ethanol, and lactate, and three non-native products: 1-butanol, 1,4-butanediol, and 1,3-propanediol. Notably, among several target candidates for cofactor engineering, glyceraldehyde-3-phosphate dehydrogenase (GAPD) is the most promising enzyme; its cofactor modification enhanced both the desired product and biomass yields significantly. Finally, given the identified target, we further discussed potential mutational strategies for modifying cofactor specificity of GAPD in E. coli as suggested by in silico protein docking experiments.