Metabolism controls gene expression through allosteric interactions between metabolites and transcription factors. These interactions are usually measured with in vitro assays, but there are no methods to identify them at a genome-scale in vivo. Here we show that dynamic transcriptome and metabolome data identify metabolites that control transcription factors in E. coli. By switching an E. coli culture between starvation and growth, we induce strong metabolite concentration changes and gene expression changes. Using Network Component Analysis we calculate the activities of 209 transcriptional regulators and correlate them with metabolites. This approach captures, for instance, the in vivo kinetics of CRP regulation by cyclic-AMP. By testing correlations between all pairs of transcription factors and metabolites, we predict putative effectors of 71 transcription factors, and validate five interactions in vitro. These results show that combining transcriptomics and metabolomics generates hypotheses about metabolism-transcription interactions that drive transitions between physiological states.