Protein phosphorylation in eukaryotes is carried out by a large and diverse family of protein kinases, which display remarkable diversity and complexity in their modes of regulation. The complex modes of regulation have evolved as a consequence of natural selection operating on protein kinase sequences for billions of years. Here we describe how quantitative comparisons of protein kinase sequences from diverse organisms, in particular prokaryotes, have contributed to our understanding of the structural organization and evolution of allosteric regulation in the protein kinase domain. An emerging view from these studies is that regulatory diversity and complexity in the protein kinase domain evolved in a 'modular' fashion through elaboration of an ancient core component, which existed before the emergence of eukaryotes. The core component provided the conformational flexibility required for ATP binding and phosphoryl transfer in prokaryotic kinases, but evolved into a highly regulatable domain in eukaryotes through the addition of exaggerated structural features that facilitated tight allosteric control. Family and group-specific features are built upon the core component in eukaryotes to provide additional layers of control. We propose that 'modularity' and 'conformational flexibility' are key evolvable traits of the protein kinase domain that contributed to its extensive regulatory diversity and complexity.