DNA microarray studies have shown that hundreds of genes are transcribed periodically during the mitotic cell cycle of humans, budding yeast, fission yeast and the plant Arabidopsis thaliana. Here we show that despite the fact the protein complexes involved in this process are largely the same among all eukaryotes, their regulation has evolved considerably. Our comparative analysis of several large-scale data sets reveals that although the regulated subunits of each protein complex are expressed just before its time of action, the identity of the periodically expressed proteins differs significantly between organisms. Moreover, we show that these changes in transcriptional regulation have co-evolved with post-translational control independently in several lineages; loss or gain of cell-cycle-regulated transcription of specific genes is often mirrored by changes in phosphorylation of the proteins that they encode. Our results indicate that many different solutions have evolved for assembling the same molecular machines at the right time during the cell cycle, involving both transcriptional and post-translational layers that jointly control the dynamics of biological systems.