The human immunodeficiency virus type 1 (HIV-1) Vif plays a crucial role in the viral life cycle by antagonizing a host restriction factor APOBEC3G (A3G). Vif interacts with A3G and induces its polyubiquitination and subsequent degradation via the formation of active ubiquitin ligase (E3) complex with Cullin5-ElonginB/C. Although Vif itself is also ubiquitinated and degraded rapidly in infected cells, precise roles and mechanisms of Vif ubiquitination are largely unknown. Here we report that MDM2, known as an E3 ligase for p53, is a novel E3 ligase for Vif and induces polyubiquitination and degradation of Vif. We also show the mechanisms by which MDM2 only targets Vif, but not A3G that binds to Vif. MDM2 reduces cellular Vif levels and reversely increases A3G levels, because the interaction between MDM2 and Vif precludes A3G from binding to Vif. Furthermore, we demonstrate that MDM2 negatively regulates HIV-1 replication in non-permissive target cells through Vif degradation. These data suggest that MDM2 is a regulator of HIV-1 replication and might be a novel therapeutic target for anti-HIV-1 drug.