Analysis of gene regulation in ESPP bacteria relies on comparisons to model organisms, and hence on assumptions about how gene regulation evolves. To test these assumptions we examined the evolutionary histories of transcription factors and of regulatory interactions from the model bacterium Escherichia coli K12. We show that although most transcription factors have paralogs, these usually arose by horizontal gene transfer rather than by duplication within the E. coli lineage, as previously believed. Most neighbor regulators -- regulators that are adjacent to genes that they regulate -- were acquired by horizontal gene transfer, while most global regulators evolved vertically within the gamma-Proteobacteria. Neighbor regulators are often acquired together with the operon that they regulate, which suggests that the proximity is maintained by repeated transfers, and also aids the prediction of the regulators' function. Because of the complex evolutionary histories of most transcription factors, bidirectional best hits tend to be misleading, and most annotations of bacterial regulators are probably incorrect. When we analyzed the histories of regulatory interactions, we found that the evolution of regulation by duplication was rare, and surprisingly, many of the regulatory interactions that are shared between paralogs result from convergent evolution. Furthermore, horizontally transferred genes are more likely than other genes to be regulated by multiple regulators, and most of this complex regulation probably evolved after the transfer. Finally, gene regulation is often not conserved, even within the gamma-Proteobacteria. Our results suggest that the bacterial regulatory network is evolving rapidly under positive selection. Such rapid rewiring of gene regulation may be crucial for adaptation to new niches.