Some protein-binding pairs exhibit extreme specificities that functionally insulate them from homologs. Such pairs evolve mostly by accumulating single-point mutations, and mutants are selected if they exhibit sufficient affinity. Until now, finding a fully functional single-mutation path connecting orthogonal pairs could only be achieved by full enumeration of intermediates and was restricted to pairs that were mutationally close. We present a computational framework for discovering single-mutation paths with low molecular strain and apply it to two orthogonal bacterial endonuclease-immunity pairs separated by 17 interfacial mutations. By including mutations that bridge identities that could not be exchanged by single-nucleotide mutations, we discovered a strain-free 19-mutation path that was fully functional in vivo. The change in binding preference occurred remarkably abruptly, resulting from only one radical mutation in each partner. Furthermore, each of the specificity-switch mutations increased fitness, demonstrating that functional divergence could be driven by positive Darwinian selection.