HIV-1 encodes the accessory protein Vif, which hijacks a host Cullin-RING ubiquitin ligase (CRL) complex as well as the non-canonical cofactor CBFβ, to antagonize APOBEC3 antiviral proteins. Non-canonical cofactor recruitment to CRL complexes by viral factors, to date, has only been attributed to HIV-1 Vif. To further study this phenomenon, we employed a comparative approach combining proteomic, biochemical, structural, and virological techniques to investigate Vif complexes across the lentivirus genus, including primate (HIV-1 and simian immunodeficiency virus macaque [SIVmac]) and non-primate (FIV, BIV, and MVV) viruses. We find that CBFβ is completely dispensable for the activity of non-primate lentiviral Vif proteins. Furthermore, we find that BIV Vif requires no cofactor and that MVV Vif requires a novel cofactor, cyclophilin A (CYPA), for stable CRL complex formation and anti-APOBEC3 activity. We propose modular conservation of Vif complexes allows for potential exaptation of functions through the acquisition of non-CRL-associated host cofactors while preserving anti-APOBEC3 activity.