FANCM is a Fanconi anemia nuclear core complex protein required for the functional integrity of the FANC-BRCA pathway of DNA damage response and repair. Here we report the isolation and characterization of two histone-fold-containing FANCM-associated proteins, MHF1 and MHF2. We show that suppression of MHF1 expression results in (1) destabilization of FANCM and MHF2, (2) impairment of DNA damage-induced monoubiquitination and foci formation of FANCD2, (3) defective chromatin localization of FA nuclear core complex proteins, (4) elevated MMC-induced chromosome aberrations, and (5) sensitivity to MMC and camptothecin. We also provide biochemical evidence that MHF1 and MHF2 assemble into a heterodimer that binds DNA and enhances the DNA branch migration activity of FANCM. These findings reveal critical roles of the MHF1-MHF2 dimer in DNA damage repair and genome maintenance through FANCM.