Transcriptional regulation enables bacteria to adjust to its environment. This is driven by transcription factors (TFs), which display DNA site recognition specificity with some flexibility built in. TFs, however, are not considered essential to a minimal cellular life. How did they evolve? It has been hypothesized that TFs evolve by gaining specificity (and other functions) on a background of non-specific chromosome structuring proteins. We used the IHF/HU family of DNA binding proteins, in which IHF binds DNA in a sequence-specific manner, whereas HU binds more indiscriminately, to test this hypothesis. We show that HUβ has been present from the bacterial root, while both IHF subunits emerged much later and diversified in Proteobacteria, with HUα having possibly arisen from transfer events in Gammaproteobacteria. By reconstructing ancestral sequences in-silico on a rooted phylogeny of IHF/HU we show that the common ancestor of this family was probably HU-like and therefore non-specific in binding DNA. IHF evolved from a branch of HU after HU had substantially diverged. Various residues characteristic of IHFα and shown to be involved in specific sequence recognition (at least in E. coli) have likely been co-opted from preexisting residues in HU, while those residues of IHFβ have likely evolved independently, suggesting that each of the IHF subunits has undergone different trajectories to acquire their DNA binding properties.