Background: The restriction factor SAMHD1, an effector of the innate immune response to viral pathogens, blocks retroviral reverse transcription in myeloid cells and resting CD4+ T-cells. Many retroviruses, including HIV-2 and other related Simian Immunodeficiency Viruses (SIVs), encode accessory genes that serve to counteract host SAMHD1 restriction by inducing the degradation of this antiviral factor. The viral accessory protein Vpr is responsible for SAMHD1 degradation in somelineages of lentiviruses, while in others, the related protein Vpx assumes this task. However, HIV-1 has no SAMHD1 degradation capability, leading to questions about whether or not there is a selective advantage to this activity. Methodology: We used an evolutionary approach to examine the importance of SAMHD1 antagonism for viral fitness by studying adaptation to host in the context of natural SIV infections. Though African Green Monkeys (AGMs) comprise four related species, each population is infected with a distinct subtype of SIVagm, providing a unique opportunity to study the evolutionary forces governing virus-host interactions. We sequenced SAMHD1 from 50 AGMs representing four host species to identify SAMHD1 polymorphism which could alter Vpr specificity. We then determined how Vpr proteins from different SIVagm subtypes are capable of mediating degradation of each of the different AGM SAMHD1 variants. Results: We found multiple SAMHD1 haplotypes in AGMs which are differentially sensitive to degradation by Vpr from SIVagm subtypes. SIVagm Vprs are capable of inducing the degradation of the major SAMHD1 alleles found in their host population, but are often incapable of degrading SAMHD1 found in other populations. The specificity of Vpr for SAMHD1 involves both the N- and C-terminal regions of SAMHD1 and this specificity has evolved independently from adaptations of other Vpr proteins for their host SAMHD1. Conclusions: We conclude that SIVagm has adapted to the SAMHD1 polymorphisms of the AGM population in which it is found. Evidence of viral adaptation to host restriction indicates that SAMHD1 antagonism is actively maintained in natural infections and that this function must be advantageous to viral fitness, despite its absence in HIV-1.