Cross-species transmission and adaptation of simian immunodeficiency viruses (SIVs) to humans have given rise to human immunodeficiency viruses (HIVs). HIV type 1 (HIV-1) and type 2 (HIV-2) were derived from SIVs that infected chimpanzee (SIVcpz) and sooty mangabey (SIVsm), respectively. The HIV-1 restriction factor SAMHD1 inhibits HIV-1 infection in human myeloid cells and can be counteracted by the Vpx protein of HIV-2 and the SIVsm lineage. However, HIV-1 and its ancestor SIVcpz do not encode a Vpx protein and HIV-1 has not evolved a mechanism to overcome SAMHD1-mediated restriction. Here we show that the co-evolution of primate SAMHD1 and lentivirus Vpx leads to the loss of the vpx gene in SIVcpz and HIV-1. We found evidence for positive selection of SAMHD1 in orangutan, gibbon, rhesus macaque, and marmoset, but not in human, chimpanzee and gorilla that are natural hosts of Vpx-negative HIV-1, SIVcpz and SIVgor, respectively, indicating that vpx drives the evolution of primate SAMHD1. Ancestral host state reconstruction and temporal dynamic analyses suggest that the most recent common ancestor of SIVrcm, SIVmnd, SIVcpz, SIVgor and HIV-1 was a SIV that had a vpx gene; however, the vpx gene of SIVcpz was lost approximately 3643 to 2969 years ago during the infection of chimpanzees. Thus, HIV-1 could not inherit the lost vpx gene from its ancestor SIVcpz. The lack of Vpx in HIV-1 results in restricted infection in myeloid cells that are important for antiviral immunity, which could contribute to the AIDS pandemic by escaping the immune responses.