FANCM remodels branched DNA structures and plays essential roles in the cellular response to DNA replication stress. Here, we show that FANCM forms a conserved DNA-remodeling complex with a histone-fold heterodimer, MHF. We find that MHF stimulates DNA binding and replication fork remodeling by FANCM. In the cell, FANCM and MHF are rapidly recruited to forks stalled by DNA interstrand crosslinks, and both are required for cellular resistance to such lesions. In vertebrates, FANCM-MHF associates with the Fanconi anemia (FA) core complex, promotes FANCD2 monoubiquitination in response to DNA damage, and suppresses sister-chromatid exchanges. Yeast orthologs of these proteins function together to resist MMS-induced DNA damage and promote gene conversion at blocked replication forks. Thus, FANCM-MHF is an essential DNA-remodeling complex that protects replication forks from yeast to human.