Archaeal/eukaryotic primases form a heterodimer consisting of a small catalytic subunit (PriS) and a large subunit (PriL). The heterodimer complex synthesizes primer oligoribonucleotides that are required for chromosomal replication. Here, we describe crystallographic and biochemical studies of the N-terminal domain (NTD) of PriL (PriL(NTD); residues 1-222) that bind to PriS from a hyperthermophilic archaeon, Pyrococcus horikoshii, at 2.9 A resolution. The PriL(NTD) structure consists of two subdomains, the helix-bundle and twisted-strand domains. The latter is structurally flexible, and is expected to contain a PriS interaction site. Pull-down and surface plasmon resonance analyses of structure-based deletion and alanine scanning mutants showed that the conserved hydrophobic Tyr155-Tyr156-Ile157 region near the flexible region is the PriS-binding site, as the Y155A/Y156A/I157A mutation markedly reduces PriS binding, by 1000-fold. These findings and a structural comparison with a previously reported PriL(NTD)-PriS complex suggest that the presented alternative conformations of the twisted-strand domain facilitate the heterodimer assembly.