The multisubunit Mediator (MED) complex bridges DNA-bound transcriptional regulators to the RNA polymerase II (PolII) initiation machinery. In yeast, the 25 MED subunits are distributed within three core subcomplexes and a separable kinase module composed of Med12, Med13 and the Cdk8-CycC pair thought to control the reversible interaction between MED and PolII by phosphorylating repeated heptapeptides within the Rpb1 carboxyl-terminal domain (CTD). Here, MED conservation has been investigated across the eukaryotic kingdom. Saccharomyces cerevisiae Med2, Med3/Pgd1 and Med5/Nut1 subunits are apparent homologs of metazoan Med29/Intersex, Med27/Crsp34 and Med24/Trap100, respectively, and these and other 30 identified human MED subunits have detectable counterparts in the amoeba Dictyostelium discoideum, indicating that none is specific to metazoans. Indeed, animal/fungal subunits are also conserved in plants, green and red algae, entamoebids, oomycetes, diatoms, apicomplexans, ciliates and the 'deep-branching' protists Trichomonas vaginalis and Giardia lamblia. Surprisingly, although lacking CTD heptads, T. vaginalis displays 44 MED subunit homologs, including several CycC, Med12 and Med13 paralogs. Such observations have allowed the identification of a conserved 17-subunit framework around which peripheral subunits may be assembled, and support a very ancient eukaryotic origin for a large, four-module MED. The implications of this comprehensive work for MED structure-function relationships are discussed.