An unexpectedly high number of regulatory RNAs have been recently discovered that fine-tune the function of genes at all levels of expression. We employed Genomic SELEX, a method to identify protein-binding RNAs encoded in the genome, to search for further regulatory RNAs in Escherichia coli. We used the global regulator protein Hfq as bait, because it can interact with a large number of RNAs, promoting their interaction. The enriched SELEX pool was subjected to deep sequencing, and 8865 sequences were mapped to the E. coli genome. These short sequences represent genomic Hfq-aptamers and are part of potential regulatory elements within RNA molecules. The motif 5'-AAYAAYAA-3' was enriched in the selected RNAs and confers low-nanomolar affinity to Hfq. The motif was confirmed to bind Hfq by DMS footprinting. The Hfq aptamers are 4-fold more frequent on the antisense strand of protein coding genes than on the sense strand. They were enriched opposite to translation start sites or opposite to intervening sequences between ORFs in operons. These results expand the repertoire of Hfq targets and also suggest that Hfq might regulate the expression of a large number of genes via interaction with cis-antisense RNAs.