Most bacterial small RNAs (sRNAs) are post-transcriptional regulators of gene expression, exerting their regulatory function by base-pairing with their target mRNAs. While it has become evident that sRNAs play central regulatory roles in the cell, little is known about their evolution and the evolution of their regulatory interactions. Here we used the prokaryotic phylogenetic tree to reconstruct the evolutionary history of Escherichia coli sRNAs and their binding sites on target mRNAs. We discovered that sRNAs currently present in E. coli mainly accumulated inside the Enterobacteriales order, succeeding the appearance of other types of noncoding RNAs and concurrently with the evolution of a variant of the Hfq protein exhibiting a longer C-terminal region. Our analysis of the evolutionary ages of sRNA-mRNA interactions revealed that while all sRNAs were evolutionarily older than most of their known binding sites on mRNA targets, for quite a few sRNAs there was at least one binding site that coappeared with or preceded them. It is conceivable that the establishment of these first interactions forced selective pressure on the sRNAs, after which additional targets were acquired by fitting a binding site to the active region of the sRNA. This conjecture is supported by the appearance of many binding sites on target mRNAs only after the sRNA gain, despite the prior presence of the target gene in ancestral genomes. Our results suggest a selective mechanism that maintained the sRNAs across the phylogenetic tree, and shed light on the evolution of E. coli post-transcriptional regulatory network.