Histidine kinases (HKs) are a central part of bacterial environmental-sensing two component systems, providing their hosts with the ability to respond to a wide range of physical and chemical signals, being a paradigmatic example of protein diversity and molecular evolution. HK are multidomain proteins consisting of at least a sensor domain, dimerization and phosphorylation domain (DHp) and a catalytic domain. They work as homodimers, and the existence of two different autophosphorylation mechanisms (cis and trans), has been proposed as relevant for pathway specificity. Although several HKs have been intensively studied, a precise sequence-to-structure explanation of why and how either cis or trans phosphorylation occurs, is still unavailable, nor is there any evolutionary analysis on the subject. In this work we show that AlphaFold can accurately determine whether a HK dimerizes in a cis or trans structure. We then use it to explore the molecular determinants of the phosphorylation mechanism. We conclude that it is the difference in lengths of the helices surrounding the DHp loop that determines the mechanism. We also show that very small changes in these helices can cause a mechanism switch, providing these systems with a way to diverge rapidly and adapt to new stimuli.