When microbes acquire new abilities through horizontal gene transfer, the genes and pathways must function under conditions with which they did not coevolve. If newly-acquired genes burden the host, their utility will depend on further evolutionary refinement of the recombinant strain. We used laboratory evolution to recapitulate this process of transfer and refinement, demonstrating that effective use of an introduced dichloromethane degradation pathway required one of several mutations to the bacterial host that are predicted to increase chloride efflux. We then used this knowledge to identify parallel, beneficial mutations that independently evolved in two natural dichloromethane-degrading strains. Finally, we constructed a synthetic mobile genetic element carrying both the degradation pathway and a chloride exporter, which preempted the adaptive process and directly enabled effective dichloromethane degradation across diverse Methylobacterium environmental isolates. Our results demonstrate the importance of post-transfer refinement in horizontal gene transfer, with potential applications in bioremediation and synthetic biology.