A complex of two proteins, Xrcc4 and DNA ligase IV, plays a fundamental role in DNA non-homologous end joining (NHEJ), a cellular function required for double-strand break repair and V(D)J recombination. Here we report the crystal structure of human Xrcc4 bound to a polypeptide that corresponds to the DNA ligase IV sequence linking its two BRCA1 C-terminal (BRCT) domains. In the complex, a single ligase chain binds asymmetrically to an Xrcc4 dimer. The helical tails of Xrcc4 undergo a substantial conformational change relative to the uncomplexed protein, forming a coiled coil that unwinds upon ligase binding, leading to a flat interaction surface. A buried network of charged hydrogen bonds surrounded by extensive hydrophobic contacts explains the observed tightness of the interaction. The strong conservation of residues at the interface between the two proteins provides evidence that the observed mode of interaction has been maintained in NHEJ throughout evolution.