Histidine kinases are key components of regulatory networks in bacteria. Although many of these enzymes are bifunctional, mediating both phosphorylation and dephosphorylation of downstream targets, the molecular details of this central regulatory switch are unclear. We showed recently that the universal second messenger cyclic di-guanosine monophosphate (c-di-GMP) drives Caulobacter crescentus cell cycle progression by forcing the cell cycle kinase CckA from its default kinase into phosphatase mode. We use a combination of structure determination, modeling, and functional analysis to demonstrate that c-di-GMP reciprocally regulates the two antagonistic CckA activities through noncovalent cross-linking of the catalytic domain with the dimerization histidine phosphotransfer (DHp) domain. We demonstrate that both c-di-GMP and ADP (adenosine diphosphate) promote phosphatase activity and propose that c-di-GMP stabilizes the ADP-bound quaternary structure, which allows the receiver domain to access the dimeric DHp stem for dephosphorylation. In silico analyses predict that c-di-GMP control is widespread among bacterial histidine kinases, arguing that it can replace or modulate canonical transmembrane signaling.