Orthologous genes in divergent species are expected to perform similar or identical functions. Recently, experimental work demonstrated that nearly half of yeast genes can be functionally replaced with their human orthologs. To understand the evolutionary constraints that lead to the replicability of orthologous proteins in highly divergent genomes we performed a set biochemically realistic simulations on interacting proteins. Using a novel method of efficient forward simulation we evolved several sets of interacting proteins under different selective, stability, and population genetic scenarios. We then evaluated their ability to bind evolutionarily divergent ancestral partners. We find that selection for protein-protein interactions preserves the ability to bind to divergent partners despite extensive sequence divergence, though eventually the accumulation of mutations causes binding incompatibilities. These findings have implications for humanizing entire cellular processes in yeast, which could simplify drug discovery and studies of human genetic polymorphisms. These findings also shed light on how the co-evolution of residues at binding interfaces maintain function over long evolutionary periods.