Lentiviral Nef proteins have multiple functions and are important for viral pathogenesis. Recently, Nef proteins from many simian immunodefiency viruses were shown to antagonize a cellular antiviral protein, named Tetherin, that blocks release of viral particles from the cell surface. However, the mechanism by which Nef antagonizes Tetherin is unknown. Here, using related Nef proteins that differ in their ability to antagonize Tetherin, we identify three amino-acids in the C-terminal domain of Nef that are critical specifically for its ability to antagonize Tetherin. Additionally, divergent Nef proteins bind to the AP-2 clathrin adaptor complex, and we show that residues important for this interaction are required for Tetherin antagonism, downregulation of Tetherin from the cell surface and removal of Tetherin from sites of particle assembly. Accordingly, depletion of AP-2 using RNA interference impairs the ability of Nef to antagonize Tetherin, demonstrating that AP-2 recruitment is required for Nef proteins to counteract this antiviral protein.