The Spt4-Spt5 complex is an essential RNA polymerase II elongation factor found in all eukaryotes and important for gene regulation. We report here the crystal structure of Saccharomyces cerevisiae Spt4 bound to the NGN domain of Spt5. This structure reveals that Spt4-Spt5 binding is governed by an acid-dipole interaction between Spt5 and Spt4. Mutations that disrupt this interaction disrupt the complex. Residues forming this pivotal interaction are conserved in the archaeal homologs of Spt4 and Spt5, which we show also form a complex. Even though bacteria lack a Spt4 homolog, the NGN domains of Spt5 and its bacterial homologs are structurally similar. Spt4 is located at a position that may help to maintain the functional conformation of the following KOW domains in Spt5. This structural and evolutionary perspective of the Spt4-Spt5 complex and its homologs suggest that it is an ancient, core component of the transcription elongation machinery.