The primate lentivirus auxiliary protein Vpx counteracts an unknown restriction factor that renders human dendritic and myeloid cells largely refractory to HIV-1 infection. Here we identify SAMHD1 as this restriction factor. SAMHD1 is a protein involved in Aicardi-Goutières syndrome, a genetic encephalopathy with symptoms mimicking congenital viral infection, that has been proposed to act as a negative regulator of the interferon response. We show that Vpx induces proteasomal degradation of SAMHD1. Silencing of SAMHD1 in non-permissive cell lines alleviates HIV-1 restriction and is associated with a significant accumulation of viral DNA in infected cells. Concurrently, overexpression of SAMHD1 in sensitive cells inhibits HIV-1 infection. The putative phosphohydrolase activity of SAMHD1 is probably required for HIV-1 restriction. Vpx-mediated relief of restriction is abolished in SAMHD1-negative cells. Finally, silencing of SAMHD1 markedly increases the susceptibility of monocytic-derived dendritic cells to infection. Our results demonstrate that SAMHD1 is an antiretroviral protein expressed in cells of the myeloid lineage that inhibits an early step of the viral life cycle.