Protein phosphorylation/dephosphorylation has long been considered a recent addition to Nature's regulatory arsenal. Early studies indicated that this molecular regulatory mechanism existed only in higher eukaryotes, suggesting that protein phosphorylation/dephosphorylation had emerged to meet the particular signal-transduction requirements of multicellular organisms. Although it has since become apparent that simple eukaryotes and even bacteria are sites of protein phosphorylation/dephosphorylation, the perception widely persists that this molecular regulatory mechanism emerged late in evolution, i.e. after the divergence of the contemporary phylogenetic domains. Only highly developed cells, it was reasoned, could afford the high ‘overhead’ costs inherent in the acquisition of dedicated protein kinases and protein phosphatases. The advent of genome sequencing has provided an opportunity to exploit Nature's phylogenetic diversity as a vehicle for critically examining this hypothesis. In tracing the origins and evolution of protein phosphorylation/dephosphorylation, the members of the Archaea, the so-called ‘third domain of life’, will play a critical role. Whereas several studies have demonstrated that archaeal proteins are subject to modification by covalent phosphorylation, relatively little is known concerning the identities of the proteins affected, the impact on their functional properties, or the enzymes that catalyse these events. However, examination of several archaeal genomes has revealed the widespread presence of several ostensibly ‘eukaryotic’ and ‘bacterial’ protein kinase and protein phosphatase paradigms. Similar findings of ‘phylogenetic trespass’ in members of the Eucarya (eukaryotes) and the Bacteria suggest that this versatile molecular regulatory mechanism emerged at an unexpectedly early point in development of ‘life as we know it'.