Recent investigations on metazoan transcription factors (TFs) indicate that single-gene duplication events and the gain and loss of protein domains are 2 crucial factors in shaping their protein-protein interaction networks. Plant genomes, on the other hand, have a history of polyploidy and whole-genome duplications (WGDs), and thus, their study helps to understand whether WGDs have also had a significant influence on protein network evolution. Here we investigate the evolution of the interaction network in the well-studied MADS domain MIKC-type proteins, a TF family which plays an important role in both the vegetative and the reproductive phases of plant life. We combine phylogenetic reconstruction, protein domain analysis, and interaction data from different species. We show that, unlike previously analyzed interaction networks, the MIKC-type protein network displays a characteristic topology, with overall high inter-subfamily connectivity, shared interactors between paralogs, and conservation of interaction patterns across species. The evaluation of the number of MIKC-type proteins at key time points throughout the evolution of land plants in the lineage leading to Arabidopsis suggested that most duplicates were retained after each round of WGD. We provide evidence that an initial network, formed by 9-11 homodimerizing proteins interacting with each other, existed in the common ancestor of all seed plants. This basic structure has been conserved after each round of WGD, adding layers of paralogs with similar interaction patterns. We thus present the first model where we can show that a network of eukaryotic TFs has evolved via rounds of WGD. Furthermore, we found that in subfamilies in which the K domain is most diverged, the interactions with other subfamilies have been largely lost. We discuss the possibility that such a high proportion of genes were retained after each WGD because of their capacity to form higher order complexes involving proteins from different subfamilies. The simultaneous duplications allowed for the conservation of the quantitative balance between the constituents and facilitated sub- and neofunctionalization through differential expression of whole units.