XRCC4 and DNA ligase IV form a complex that is essential for the repair of all double-strand DNA breaks by the nonhomologous DNA end joining pathway in eukaryotes. We find here that human XRCC4:DNA ligase IV can ligate two double-strand DNA ends that have fully incompatible short 3' overhang configurations with no potential for base pairing. Moreover, at DNA ends that share 1-4 annealed base pairs, XRCC4:DNA ligase IV can ligate across gaps of 1 nt. Ku can stimulate the joining, but is not essential when there is some terminal annealing. Polymerase mu can add nucleotides in a template-independent manner under physiological conditions; and the subset of ends that thereby gain some terminal microhomology can then be ligated. Hence, annealing at sites of microhomology is very important, but the flexibility of the ligase complex is paramount in nonhomologous DNA end joining. These observations provide an explanation for several in vivo observations that were difficult to understand previously.