Histone-fold proteins typically assemble in multiprotein complexes to bind duplex DNA. However, one histone-fold complex, MHF, associates with Fanconi anemia (FA) protein FANCM to form a branched DNA remodeling complex that senses and repairs stalled replication forks and activates FA DNA damage response network. How the FANCM-MHF complex recognizes branched DNA is unclear. Here, we solved the crystal structure of MHF and its complex with the MHF-interaction domain (referred to as MID) of FANCM, and performed structure-guided mutagenesis. We found that the MID-MHF complex consists of one histone H3-H4-like MHF heterotetramer wrapped by a single polypeptide of MID. We identified a zinc atom-liganding structure at the central interface between MID and MHF that is critical for stabilization of the complex. Notably, the DNA-binding surface of MHF was altered by MID in both electrostatic charges and allosteric conformation. This leads to a switch in the DNA-binding preference - from duplex DNA by MHF alone, to branched DNA by the MID-MHF complex. Mutations that disrupt either the composite DNA-binding surface or the protein-protein interface of the MID-MHF complex impaired activation of the FA network and genome stability. Our data provide the structural basis of how FANCM and MHF work together to recognize branched DNA, and suggest a novel mechanism by which histone-fold complexes can be remodeled by their partners to bind special DNA structures generated during DNA metabolism.