Distinguishing self from non-self is a fundamental biological challenge. Many pathogens exploit the challenge of self discrimination by employing mimicry to subvert key cellular processes including the cell cycle, apoptosis and cytoskeletal dynamics. Other mimics interfere with immunity. Poxviruses encode K3L, a mimic of eIF2alpha, which is the substrate of protein kinase R (PKR), an important component of innate immunity in vertebrates. The PKR-K3L interaction exemplifies the conundrum imposed by viral mimicry. To be effective, PKR must recognize a conserved substrate (eIF2alpha) while avoiding rapidly evolving substrate mimics such as K3L. Using the PKR-K3L system and a combination of phylogenetic and functional analyses, we uncover evolutionary strategies by which host proteins can overcome mimicry. We find that PKR has evolved under intense episodes of positive selection in primates. The ability of PKR to evade viral mimics is partly due to positive selection at sites most intimately involved in eIF2alpha recognition. We also find that adaptive changes on multiple surfaces of PKR produce combinations of substitutions that increase the odds of defeating mimicry. Thus, although it can seem that pathogens gain insurmountable advantages by mimicking cellular components, host factors such as PKR can compete in molecular 'arms races' with mimics because of evolutionary flexibility at protein interaction interfaces challenged by mimicry.