Summary The human SAMHD1 protein potently restricts lentiviral infection in dendritic cells and monocyte/macrophages but is antagonized by the primate lentiviral protein Vpx, which targets SAMHD1 for degradation. However, only two of eight primate lentivirus lineages encode Vpx, whereas its paralog, Vpr, is conserved across all extant primate lentiviruses. We find that not only multiple Vpx but also some Vpr proteins are able to degrade SAMHD1, and such antagonism led to dramatic positive selection of SAMHD1 in the primate subfamily Cercopithecinae. Residues that have evolved under positive selection precisely determine sensitivity to Vpx/Vpr degradation and alter binding specificity. By overlaying these functional analyses on a phylogenetic framework of Vpr and Vpx evolution, we can decipher the chronology of acquisition of SAMHD1-degrading abilities in lentiviruses. We conclude that vpr neofunctionalized to degrade SAMHD1 even prior to the birth of a separate vpx gene, thereby initiating an evolutionary arms race with SAMHD1.