The human immunodeficiency virus (HIV)-1 protein Vif has a central role in the neutralization of host innate defences by hijacking cellular proteasomal degradation pathways to subvert the antiviral activity of host restriction factors; however, the underlying mechanism by which Vif achieves this remains unclear. Here we report a crystal structure of the Vif-CBF-β-CUL5-ELOB-ELOC complex. The structure reveals that Vif, by means of two domains, organizes formation of the pentameric complex by interacting with CBF-β, CUL5 and ELOC. The larger domain (α/β domain) of Vif binds to the same side of CBF-β as RUNX1, indicating that Vif and RUNX1 are exclusive for CBF-β binding. Interactions of the smaller domain (α-domain) of Vif with ELOC and CUL5 are cooperative and mimic those of SOCS2 with the latter two proteins. A unique zinc-finger motif of Vif, which is located between the two Vif domains, makes no contacts with the other proteins but stabilizes the conformation of the α-domain, which may be important for Vif-CUL5 interaction. Together, our data reveal the structural basis for Vif hijacking of the CBF-β and CUL5 E3 ligase complex, laying a foundation for rational design of novel anti-HIV drugs.