The multifunctional Nef protein of primate lentiviruses is commonly considered an early viral factor that down-modulates various receptors from the cell surface and modulates several signaling pathways to facilitate viral immune evasion and to render the cell conducive for viral replication. However, Nef also acts during the late stages of infection, e.g. by increasing the infectivity of progeny virions. Just recently, it has become clear that many primate lentiviruses that have been detected in about 40 different monkey and ape species also use Nef to antagonize tetherin (BST2/CD317), a cellular factor that inhibits virus release by tethering nascent viral particles to the cell surface. Exceptions are some simian immunodeficiency viruses (SIVs) infecting Cercopithecus monkeys that employ their accessory Vpu protein to counteract the restriction by tetherin. Furthermore, pandemic HIV-1 group M strains switched from Nef to Vpu and HIV-2 group A isolates from Nef to Env after zoonotic transmission from chimpanzees and sooty mangabeys, respectively, to antagonize the tetherin restriction in humans. These evolutionary switches were most likely enforced by a deletion in the cytoplasmic domain of the human tetherin orthologue that confers resistance to Nef. Here, we summarize some of our current knowledge about Nef-mediated tetherin antagonism.