Mediator is a large, modular protein complex remotely conserved from yeast to man that conveys regulatory signals from DNA-binding transcription factors to RNA polymerase II. In Saccharomyces cerevisiae, Mediator is thought to be composed of 24 subunits organized in four sub-complexes, termed the head, middle, tail and Cdk8 (Srb8-11) modules. In this work, we have used screening and pair-wise two-hybrid approaches to investigate protein-protein contacts between budding yeast Mediator subunits. The derived interaction map includes the delineation of numerous interaction domains between Mediator subunits, frequently corresponding to segments that have been conserved in evolution, as well as novel connections between the Cdk8 (Srb8-11) and head modules, the head and middle modules, and the middle and tail modules. The two-hybrid analysis, together with co-immunoprecipitation studies and gel filtration experiments revealed that Med31 (Soh1) is associated with the yeast Mediator that therefore comprises 25 subunits. Finally, analysis of the protein interaction network within the Drosophila Mediator middle module indicated that the structural organization of the Mediator complex is conserved from yeast to metazoans. The resulting interaction map provides a framework for delineating Mediator structure-function and investigating how Mediator function is regulated.