The combination of genomic, proteomic and other data, enables to reconstruct the evolution of complex cellular units thus transcending the more reductionistic view of traditional molecular phylogeny. However, most models which try to investigate the evolution of protein interaction networks so far are based on the analysis of their global statistical properties, such as their scale-free behaviour. We have investigated phylogenies of three families of ancient eukaryotic transcription factors for which fairly reliable interaction data are available. For all three families, bZIP, bHLH and NR (nuclear receptors), we find that homo-dimerising proteins were probably the ancestors and that series of single gene duplications, in combination with domain-rearrangements, were the main driving force in establishing the basic network architecture. However, the overall scaling behaviour does not always precisely confer to some theoretical models on network evolution. In conclusion, new models which reflect the biological details of molecular evolution, need to be developed.