Here we use an optimization cross-linking mass spectrometry (XL-MS) pipeline for the structural characterization of a dynamic HIV-host protein complex. Using DSSO-based XL-MS analysis, residue-protein proximity restraints based on functional genetics, and integrative modeling, we define the structure of the HIV-1 Vif protein bound to restriction factor APOBEC3G (A3G), the Cullin-5 E3 ring ligase (CRL5), and the cellular transcription factor Core Binding Factor Beta (CBFβ). Using a XL-MS3 methodology, we identify 132 inter-linked peptides and integrate the data with atomic structures of the subunits and mutagenesis data, and computed an integrative structure model of the heptameric A3G-CRL5-Vif-CBFβ complex. The resulting model ensemble quantifies the dynamic heterogenity of the A3G C-terminal domain, as well as CUL5 flexibility, and defines the interface between Vif and A3G. Our model can be used to rationalize previous structural, mutatagenesis, and functional data not included in modeling. The experimental and computational approach described here is generally applicable to other challenging host-pathogen protein complexes and provides new visualization tools for characterizing cross-linking data.