SAMHD1 has recently been identified as an HIV-1 restriction factor operating in myeloid cells. As a countermeasure, the Vpx accessory protein from HIV-2 and certain lineages of SIV have evolved to antagonize SAMHD1 by inducing its ubiquitin-proteasome-dependent degradation. Here, we show that SAMHD1 experienced strong positive selection episodes during primate evolution that occurred in the Catarrhini ancestral branch prior to the separation between hominoids (gibbons and great apes) and Old World monkeys. The identification of SAMHD1 residues under positive selection led to mapping the Vpx-interaction domain of SAMHD1 to its C-terminal region. Importantly, we found that while SAMHD1 restriction activity toward HIV-1 is evolutionarily maintained, antagonism of SAMHD1 by Vpx is species-specific. The distinct evolutionary signature of SAMHD1 sheds light on the development of its antiviral specificity.