Transcription initiation is regulated by transcription factors (TFs). Though TFs determine phenotype, they are nonessential for minimal cellular life. Given this and the idea that it is a certain level of organism “complexity” that calls for transcription regulation, we traced the evolution of TF repertoire on a bacterio-archaeal phylogeny using a dataset of ∼500,000 TFs. The most ancestral prokaryotes probably encoded multiple TFs. These, based on functions of extant relatives, possibly regulated sugar-fermentation metabolism, sensed overall metabolic state and redox, responded to DNA damage or bound metals; many of which are consistent with some reconstructions of ancestral gene pools and physiologies. The number of TFs and their superfamily-level diversity, through evolutionary history, are similar to those in extant bacteria. These suggest pre-LUCA diversification of TF families. Emergence of new TFs along the phylogeny shows innovation early in prokaryote evolution, in contrast to eukaryotes, in which many TF families emerged in bursts at multicellular lineages. Gains of TFs late in prokaryotic evolution appear to be products of horizontal acquisition of proteins discovered earlier along some other lineage. We speculate on the difference between the evolutionary trajectory of prokaryotic and eukaryotic TF repertoire and how this might be explained by how complexity is envisioned in these two different kingdoms.