Human immunodeficiency virus type 1 (HIV-1) Vif requires core binding factor β (CBF-β) to degrade the host APOBEC3 restriction factors. Although a minimum domain and certain amino acids of HIV-1 Vif, including hydrophobic residues at the N-terminal, have been identified as critical sites for binding with CBF-β, other regions that potentially mediate this interaction need to be further investigated. Here, we mapped two new regions of HIV-1 Vif that are required for interaction with CBF-β by generating a series of single-site or multiple-site Vif mutants and testing their effect on the suppression of APOBEC3G (A3G) and APOBEC3F (A3F). A number of the mutants, including G84A/SIEW86-89AAAA (84/86-89), E88A/W89A (88/89), G84A, W89A, L106S and I107S in the 84GxSIEW89 and L102ADQLI107 regions, affected Vif function by disrupting CBF-β binding. These Vif mutants also had altered interactions with CUL5, since CBF-β is known to facilitate the binding of Vif to CUL5. We further showed that this effect was not due to misfolding or conformational changes in Vif, as the mutants still maintained their interactions with other factors such as ElonginB, A3G and A3F. Notably, G84D and D104A had stronger effects on the Vif-CUL5 interaction than on the Vif-CBF-β interaction, indicating that they mainly influenced the CUL5 interaction and implying that the interaction of Vif with CUL5 contributes to the binding of Vif to CBF-β. These new binding interfaces with CBF-β in HIV-1 Vif provide novel targets for the development of HIV-1 inhibitors.