Human cytidine deaminase APOBEC3C (A3C) acts as a potent inhibitor of SIVagm and can be regulated by both HIV-1 and SIVagm Vif. The mechanism by which Vif suppresses A3C is unknown. In the present study, we demonstrate that both HIV-1 and SIVagm Vif can act in a proteasome-dependent manner to overcome A3C. SIVagm Vif requires the Cullin5-ElonginB-ElonginC E3 ubiquitin ligase for the degradation of A3C as well as the suppression of its antiviral activity. Mutation of a residue critical for the species-specific recognition of human or monkey A3G by HIV-1 Vif or SIVagm Vif in A3C had little effect on HIV-1 or SIVagm Vif-mediated degradation of A3C. Although the amino-terminal region of A3G was not important for Vif-mediated degradation, the corresponding region in A3C was critical. A3C mutants that were competent for Vif binding but resistant to Vif-mediated degradation were identified. These data suggest that primate lentiviral Vif molecules have evolved to recognize multiple host APOBEC3 proteins through distinct mechanisms. However, Cul5-E3 ubiquitin ligase appears to be a common pathway hijacked by HIV-1 and SIV Vif to defeat APOBEC3 proteins. Furthermore, Vif and APOBEC3 binding is not sufficient for target protein degradation indicating an important but uncharacterized Vif function.