DNA interstrand crosslinks (ICLs) are highly toxic because they block the progression of replisomes. The Fanconi Anemia (FA) proteins, encoded by genes that are mutated in FA, are important for repair of ICLs. The FA core complex catalyzes the monoubiquitination of FANCD2, and this event is essential for several steps of ICL repair. However, how monoubiquitination of FANCD2 promotes ICL repair at the molecular level is unknown. Here, we describe a highly conserved protein, KIAA1018/MTMR15/FAN1, that interacts with, and is recruited to sites of DNA damage by, the monoubiquitinated form of FANCD2. FAN1 exhibits endonuclease activity toward 5' flaps and has 5' exonuclease activity, and these activities are mediated by an ancient VRR_nuc domain. Depletion of FAN1 from human cells causes hypersensitivity to ICLs, defects in ICL repair, and genome instability. These data at least partly explain how ubiquitination of FANCD2 promotes DNA repair.