Recent bioinformatics-aided searches have identified many new small RNAs (sRNAs) in the intergenic regions of the bacterium Escherichia coli. Here, a shot-gun cloning approach (RNomics) was used to generate cDNA libraries of small sized RNAs. Besides many of the known sRNAs, we found new species that were not predicted previously. The present work brings the number of sRNAs in E.coli to 62. Experimental transcription start site mapping showed that some sRNAs were encoded from independent genes, while others were processed from mRNA leaders or trailers, indicative of a parallel transcriptional output generating sRNAs co-expressed with mRNAs. Two of these RNAs (SroA and SroG) consist of known (THI and RFN) riboswitch elements. We also show that two recently identified sRNAs (RyeB and SraC/RyeA) interact, resulting in RNase III-dependent cleavage. To the best of our knowledge, this represents the first case of two non-coding RNAs interacting by a putative antisense mechanism. In addition, intracellular metabolic stabilities of sRNAs were determined, including ones from previous screens. The wide range of half-lives (32 min) indicates that sRNAs cannot generally be assumed to be metabolically stable. The experimental characterization of sRNAs analyzed here suggests that the definition of an sRNA is more complex than previously assumed.