Organisms orchestrate cellular functions through transcription factor (TF) interactions with their target genes, although these regulatory relationships are largely unknown in most species. Here we report a high-throughput approach for characterizing TF-target gene interactions across species and its application to 354 TFs across 48 bacteria, generating 17,000 genome-wide binding maps. This dataset revealed themes of ancient conservation and rapid evolution of regulatory modules. We observed rewiring, where the TF sensing and regulatory role is maintained while the arrangement and identity of target genes diverges, in some cases encoding entirely new functions. We further integrated phenotypic information to define new functional regulatory modules and pathways. Finally, we identified 242 new TF DNA binding motifs, including a 70% increase of known Escherichia coli motifs and the first annotation in Pseudomonas simiae, revealing deep conservation in bacterial promoter architecture. Our method provides a versatile tool for functional characterization of genetic pathways in prokaryotes and eukaryotes.