During coevolution with the host, HIV-1 developed the ability to hijack the cellular ubiquitin/proteasome degradation pathway to counteract the antiviral activity of APOBEC3G (A3G), a host cytidine deaminase that can block HIV-1 replication. Abrogation of A3G function involves the HIV-1 Vif protein, which binds A3G and serves as an adapter molecule to recruit A3G to a Cullin5-based E3 ubiquitin ligase complex. Structure-guided mutagenesis of A3G focused on the 14 most surface-exposed Lys residues allowed us to identify four Lys residues (Lys-297, 301, 303, and 334) that are required for Vif-mediated A3G ubiquitination and degradation. Substitution of Arg for these residues confers Vif resistance and restores A3G's antiviral activity in the presence of Vif. In our model, the critical four Lys residues cluster at the C terminus, opposite to the known N-terminal Vif-interaction region in the protein. Thus, spatial constraints imposed by the E3 ligase complex may be an important determinant in Vif-dependent A3G ubiquitination.