By shaping gene expression profiles, small RNAs (sRNAs) enable bacteria to efficiently adapt to changes in their environment. To better understand how Escherichia coli acclimatizes to nutrient availability, we performed UV cross-linking, ligation and sequencing of hybrids (CLASH) to uncover Hfq-associated RNA-RNA interactions at specific growth stages. We demonstrate that Hfq CLASH robustly captures bona fide RNA-RNA interactions. We identified hundreds of novel sRNA base-pairing interactions, including many sRNA-sRNA interactions and involving 3’UTR-derived sRNAs. We rediscovered known and identified novel sRNA seed sequences. The sRNA-mRNA interactions identified by CLASH have strong base-pairing potential and are highly enriched for complementary sequence motifs, even those supported by only a few reads. Yet, steady state levels of most mRNA targets were not significantly affected upon over-expression of the sRNA regulator. Our results reinforce the idea that the reproducibility of the interaction, not base-pairing potential, is a stronger predictor for a regulatory outcome.