© 2015 The Authors. 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. How viral proteins evolve functions without compromising ancestral ones is not well understood. Kane etal. now report that the lentiviral protein Vif has evolved to hijack host factors in a lineage-specific manner while conserving an ancestral viral-host complex promoting viral infection.