Signal transduction in microorganisms and plants is often mediated by His-Asp phosphorelay systems. Two conserved families of proteins are centrally involved: histidine protein kinases and phospho-aspartyl response regulators. The kinases generally function in association with sensory elements that regulate their activities in response to environmental signals. A sequence analysis with 348 histidine kinase domains reveals that this family consists of distinct subgroups. A comparative sequence analysis with 298 available receiver domain sequences of cognate response regulators demonstrates a significant correlation between kinase and regulator subfamilies. These findings suggest that different subclasses of His-Asp phosphorelay systems have evolved independently of one another.