Genes encoding proteins that carry out essential informational tasks in the cell, in particular where multiple interaction partners are involved, are less likely to be transferable to a foreign organism. Here, we investigated the constraints on transfer of a gene encoding a highly conserved informational protein, translation elongation factor Tu (EF-Tu), by systematically replacing the endogenous tufA gene in the Escherichia coli genome with its extant and ancestral homologs. The extant homologs represented tuf variants from both near and distant homologous organisms. The ancestral homologs represented phylogenetically resurrected tuf sequences dating from 0.7 to 3.6 billion years ago (bya). Our results demonstrate that all of the foreign tuf genes are transferable to the E. coli genome, provided that an additional copy of the EF-Tu gene, tufB, remains present in the E. coli genome. However, when the tufB gene was removed, only the variants obtained from the gammaproteobacterial family (extant and ancestral) supported growth which demonstrates the limited functional interchangeability of E. coli tuf with its homologs. Relative bacterial fitness correlated with the evolutionary distance of the extant tuf homologs inserted into the E. coli genome. This reduced fitness was associated with reduced levels of EF-Tu and reduced rates of protein synthesis. Increasing the expression of tuf partially ameliorated these fitness costs. In summary, our analysis suggests that the functional conservation of protein activity, the amount of protein expressed, and its network connectivity act to constrain the successful transfer of this essential gene into foreign bacteria.