The archetypal two-component signal transduction systems include a sensor histidine kinase and a response regulator, which consists of a receiver CheY-like domain and a DNA-binding domain. Sequence analysis of the sensor kinases and response regulators encoded in complete bacterial and archaeal genomes revealed complex domain architectures for many of them and allowed the identification of several novel conserved domains, such as PAS, GAF, HAMP, GGDEF, EAL, and HD-GYP. All of these domains are widely represented in bacteria, including 19 copies of the GGDEF domain and 17 copies of the EAL domain encoded in the Escherichia coli genome. In contrast, these novel signaling domains are much less abundant in bacterial parasites and in archaea, with none at all found in some archaeal species. This skewed phyletic distribution suggests that the newly discovered complexity of signal transduction systems emerged early in the evolution of bacteria, with subsequent massive loss in parasites and some horizontal dissemination among archaea. Only a few proteins containing these domains have been studied experimentally, and their exact biochemical functions remain obscure; they may include transformations of novel signal molecules, such as the recently identified cyclic diguanylate. Recent experimental data provide the first direct evidence of the participation of these domains in signal transduction pathways, including regulation of virulence genes and extracellular enzyme production in the human pathogens Bordetella pertussis and Borrelia burgdorferi and the plant pathogen Xanthomonas campestris. Gene-neighborhood analysis of these new domains suggests their participation in a variety of processes, from mercury and phage resistance to maintenance of virulence plasmids. It appears that the real picture of the complexity of phosphorelay signal transduction in prokaryotes is only beginning to unfold.