The non-homologous end-joining (NHEJ) pathway repairs DNA double-strand breaks (DSBs) in all domains of life. Archaea and bacteria utilize a conserved set of multifunctional proteins in a pathway termed Archaeo-Prokaryotic (AP) NHEJ that facilitates DSB repair. Archaeal NHEJ polymerases (Pol) are capable of strand displacement synthesis, whilst filling DNA gaps or partially annealed DNA ends, which can give rise to unligatable intermediates. However, an associated NHEJ phosphoesterase (PE) resects these products to ensure that efficient ligation occurs. Here, we describe the crystal structures of these archaeal (Methanocella paludicola) NHEJ nuclease and polymerase enzymes, demonstrating their strict structural conservation with their bacterial NHEJ counterparts. Structural analysis, in conjunction with biochemical studies, has uncovered the molecular basis for DNA strand displacement synthesis in AP-NHEJ, revealing the mechanisms that enable Pol and PE to displace annealed bases to facilitate their respective roles in DSB repair.