Promoter-proximal pausing of RNA polymerase II (Pol II) is a key regulatory step during transcription. Despite the central role of pausing in gene regulation, we do not understand the evolutionary processes that led to the emergence of Pol II pausing or its transition to a rate-limiting step actively controlled by transcription factors. Here we analyzed transcription in species across the tree of life. We found that unicellular eukaryotes display a slow acceleration of Pol II near transcription start sites. This proto-paused-like state transitioned to a longer, focused pause in derived metazoans which coincided with the evolution of new subunits in the NELF and 7SK complexes. Depletion of NELF reverts the mammalian focal pause to a proto-pause-like state and compromises transcriptional activation for a set of heat shock genes. Collectively, this work details the evolutionary history of Pol II pausing and sheds light on how new transcriptional regulatory mechanisms evolve.