Host cells impose a broad range of obstacles to the replication of retroviruses. Tetherin (also known as CD317, BST-2 or HM1.24) impedes viral release by retaining newly budded HIV-1 virions on the surface of cells. HIV-1 Vpu efficiently counteracts this restriction. Here, we show that HIV-1 Vpu induces the depletion of tetherin from cells. We demonstrate that this phenomenon correlates with the ability of Vpu to counteract the antiviral activity of both overexpressed and interferon-induced endogenous tetherin. In addition, we show that Vpu co-immunoprecipitates with tetherin and beta-TrCP in a tri-molecular complex. This interaction leads to Vpu-mediated proteasomal degradation of tetherin in a beta-TrCP2-dependent manner. Accordingly, in conditions where Vpu-beta-TrCP2-tetherin interplay was not operative, including cells stably knocked down for beta-TrCP2 expression or cells expressing a dominant negative form of beta-TrCP, the ability of Vpu to antagonize the antiviral activity of tetherin was severely impaired. Nevertheless, tetherin degradation did not account for the totality of Vpu-mediated counteraction against the antiviral factor, as binding of Vpu to tetherin was sufficient for a partial relief of the restriction. Finally, we show that the mechanism used by Vpu to induce tetherin depletion implicates the cellular ER-associated degradation (ERAD) pathway, which mediates the dislocation of ER membrane proteins into the cytosol for subsequent proteasomal degradation. In conclusion, we show that Vpu interacts with tetherin to direct its beta-TrCP2-dependent proteasomal degradation, thereby alleviating the blockade to the release of infectious virions. Identification of tetherin binding to Vpu provides a potential novel target for the development of drugs aimed at inhibiting HIV-1 replication.