Mediator, the multisubunit complex that plays an essential role in the regulation of transcription initiation in all eukaryotes, was isolated using an affinity purification protocol that yields pure material suitable for structural analysis. Conformational sorting of yeast Mediator single-particle images characterized the inherent flexibility of the complex and made possible calculation of a cryo-EM reconstruction. Comparison of free and RNA polymerase II (RNAPII) -associated yeast Mediator reconstructions demonstrates that intrinsic flexibility allows structural modules to reorganize and establish a complex network of contacts with RNAPII. We demonstrate that, despite very low sequence homology, the structures of human and yeast Mediators are surprisingly similar and the structural rearrangement that enables interaction of yeast Mediator with RNAPII parallels the structural rearrangement triggered by interaction of human Mediator with a nuclear receptor. This suggests that the topology and structural dynamics of Mediator constitute important elements of a conserved regulation mechanism.