When a microbe acquires new genetic material through horizontal gene transfer or synthetic biology, genes must function in an environment with which they did not co-evolve. Efficient use of a new ability will require careful integration into the existing metabolic and regulatory networks of the host. The interactions between gene and host, as well as their evolutionary outcomes, will determine whether a microbe can become pathogenic, remediate a polluted site, or produce a biofuel. Understanding these interactions and the strategies by which evolution optimizes them will allow us to better anticipate and control the emergence of new microbial phenotypes. I will demonstrate how a combination of rational and evolutionary approaches targeted to both an enzyme and its host can be used to increase the activity of a heterologous monooxygenase by more than 50-fold. Next, I will discuss the need for evolutionary refinement of horizontally-transferred genes, using dichloromethane catabolism in Methylobacterium extorquens as a model system. By contrasting these two examples, I will show how engineering tools can provide new insight into natural evolutionary processes and how evolutionary microbiology can provide new strategies for forward engineering. Finally, I will discuss future directions in this area, with applications ranging from bioremediation to the evolutionary microbiology of pathogenesis.