The MADS-box encodes a novel type of DNA-binding domain found so far in a diverse group of transcription factors from yeast, animals, and seed plants. Here, our first aim was to evaluate the primary structure of the MADS-box. Compilation of the 107 currently available MADS-domain sequences resulted in a signature which can strictly discriminate between genes possessing or lacking a MADS-domain and allowed a classification of MADS-domain proteins into several distinct subfamilies. A comprehensive phylogenetic analysis of known eukaryotic MADS-box genes, which is the first comprising animal as well as fungal and plant homologs, showed that the vast majority of subfamily members appear on distinct subtrees of phylogenetic trees, suggesting that subfamilies represent monophyletic gene clades and providing the proposed classification scheme with a sound evolutionary basis. A reconstruction of the history of the MADS-box gene subfamilies based on the taxonomic distribution of contemporary subfamily members revealed that each subfamily comprises highly conserved putative orthologs and recent paralogs. Some subfamilies must be very old (1,000 MY or more), while others are more recent. In general, subfamily members tend to share highly similar sequences, expression patterns, and related functions. The defined species distribution, specific function, and strong evolutionary conservation of the members of most subfamilies suggest that the establishment of different subfamilies was followed by rapid fixation and was thus highly advantageous during eukaryotic evolution. These gene subfamilies may have been essential prerequisites for the establishment of several complex eukaryotic body structures, such as muscles in animals and certain reproductive structures in higher plants, and of some signal transduction pathways. Phylogenetic trees indicate that after establishment of different subfamilies, additional gene duplications led to a further increase in the number of MADS-box genes. However, several molecular mechanisms of MADS-box gene diversification were used to a quite different extent during animal and plant evolution. Known plant MADS-domain sequences diverged much faster than those of animals, and gene duplication and sequence diversification were extensively used for the creation of new genes during plant evolution, resulting in a relatively large number of interacting genes. In contrast, the available data on animal genes suggest that increase in gene number was only moderate in the lineage leading to mammals, but in the case of MEF2-like gene products, heterodimerization between different splice variants may have increased the combinatorial possibilities of interactions considerably. These observations demonstrate that in metazoan and plant evolution, increased combinatorial possibilities of MADS-box gene product interactions correlated with the evolution of increasingly complex body plans.