Myxovirus resistance protein B (MxB) is an interferon-inducible restriction factor of HIV-1 that blocks nuclear import of the viral genome. Evidence suggests that MxB recognizes higher-order interfaces of the HIV capsid lattice, but the mechanistic details of this interaction are not known. Previous studies have mapped the restriction activity of MxB to its N-terminus encompassing a triple arginine motif 11RRR13. Here we demonstrate a direct and specific interaction between the MxB N-terminus and helical assemblies of HIV-1 capsid protein (CA) using highly purified recombinant proteins. We performed thorough mutagenesis to establish the detailed molecular requirements for the CA interaction with MxB. The results map MxB binding to the interface of three CA hexamers, specifically interactions between positively charged MxB N-terminal residues and negatively charged CA residues. Our crystal structures show that the CA mutations affecting MxB interaction and restriction do not alter the conformation of capsid assembly. In addition, 30 microsecond long all-atom molecular dynamics (MD) simulations of the complex between the MxB N-terminus and the HIV CA tri-hexamer interface show persistent MxB binding and identify a MxB-binding pocket surrounded by three CA hexamers. These results establish the molecular details of the binding of a lattice-sensing host factor onto HIV capsid, and provide insight into how MxB recognizes HIV capsid for the restriction of HIV-1 infection.