Human APOBEC3G (hA3G) is a restriction factor that inhibits human immunodeficiency 1 virus (HIV-1) replication. The virally encoded protein Vif binds to hA3G and induces its degradation, thereby counteracting the antiviral activity of hA3G. Vif-mediated hA3G degradation clearly represents a potential target for anti-HIV drug development. Herein, we have performed virtual screening to discover small molecule inhibitors that target the binding interface of the Vif/hA3G complex. Subsequent biochemical studies have led to the identification of a small molecule inhibitor, IMB-301 that binds to hA3G, interrupts the hA3G-Vif interaction and inhibits Vif-mediated degradation of hA3G. As a result, IMB-301 strongly inhibits HIV-1 replication in a hA3G-dependent manner. Our study further demonstrates the feasibility of inhibiting HIV replication by abrogating the Vif-hA3G interaction with small molecules.