Methylotrophic bacteria utilize methanol and other reduced one-carbon compounds as their sole source of carbon and energy. For this purpose, these bacteria evolved a number of specialized enzymes and pathways. Here, we used a synthetic biology approach to select and introduce a set of “methylotrophy genes” into Escherichia coli based on in silico considerations and flux balance analysis to enable methanol dissimilation and assimilation. We determined that the most promising approach allowing the utilization of methanol was the implementation of NAD-dependent methanol dehydrogenase and the establishment of the ribulose monophosphate cycle by expressing the genes for hexulose-6-phosphate synthase (Hps) and 6-phospho-3-hexuloisomerase (Phi). To test for the best-performing enzymes in the heterologous host, a number of enzyme candidates from different donor organisms were selected and systematically analyzed for their in vitro and in vivo activities in E. coli. Among these, Mdh2, Hps and Phi originating from Bacillus methanolicus were found to be the most effective. Labeling experiments using 13C methanol with E. coli producing these enzymes showed up to 40% incorporation of methanol into central metabolites. The presence of the endogenous glutathione-dependent formaldehyde oxidation pathway of E. coli did not adversely affect the methanol conversion rate. Taken together, the results of this study represent a major advancement towards establishing synthetic methylotrophs by gene transfer.