Human immunodeficiency virus type 1 (HIV-1) and simian immunodeficiency virus (SIV) viral infectivity factor (Vif) form a CRL5 E3 ubiquitin ligase complex to suppress virus restriction by host APOBEC3 (A3) proteins. The primate lentiviral Vif complex is composed of the unique cofactor core binding factor β (CBF-β) and canonical ligase components Cullin 5 (CUL5), Elongin B/C (ELOB/C), and RBX2. However, the mechanism by which the Vif protein of the related lentivirus bovine immunodeficiency virus (BIV) overcomes its host A3 proteins is less clear. In this study, we show that BIV Vif interacts with Cullin 2 (CUL2), ELOB/C, and RBX1, but not with CBF-β or CUL5, to form a CRL2 E3 ubiquitin ligase and degrade the restrictive bovine A3 proteins (A3Z2Z3 and A3Z3). RNA interference-mediated knockdown of ELOB or CUL2 inhibited BIV Vif-mediated degradation of these A3 proteins, whereas knockdown of CUL5 or CBF-β did not. BIV Vif with mutations in the BC box (Vif SLQAAA) or putative VHL box (Vif YI-AA), which cannot interact with ELOB/C or CUL2, respectively, lost the ability to counteract bovine A3 proteins. Moreover, CUL2 and UBE2M dominant negative mutants competitively inhibited the BIV Vif-mediated degradation mechanism. Thus, although the general strategy for inhibiting A3 proteins is conserved between HIV-1/SIV and BIV, the precise mechanisms can differ substantially, with only the HIV-1/SIV Vif proteins requiring CBF-βas a cofactor, HIV-1/SIV Vif using CUL5-RBX2, and BIV Vif using CUL2-RBX1.