APOBEC3G (A3G) and related cytidine deaminases are potent inhibitors of retroviruses. HIV-1 Vif hijacks the cellular Cul5-E3 ubiquitin ligase to degrade APOBEC3 proteins and render them ineffective against these viruses. Here, we report that HIV-1 Vif is a novel zinc-binding protein containing an H-x(5)-C-x(17-18)-C-x(3-5)-H motif that is distinct from other recognized classes of zinc fingers. Zinc-binding stabilized a conserved hydrophobic interface within the HCCH motif that is critical for Vif-Cul5 E3 assembly and Vif function. An N-terminal region in the first Cullin repeat of Cul5, which is dispensable for adaptor ElonginC binding, was required for interaction with Vif. This region is the most divergent sequence between Cul2 and Cul5, a factor that may contribute to the selection of Cul5 and not Cul2 by Vif. This is the first example of a zinc-binding substrate receptor responsible for the assembly of a Cullin-RING ligase, representing a new target for antiviral development.