Over the past few years, techniques have been developed that have allowed the study of transcriptomes without bias from previous genome annotations, which has led to the discovery of a plethora of unexpected RNAs that have no obvious coding capacities. There are many different kinds of products that are generated by this pervasive transcription; this Review focuses on small non-coding RNAs (ncRNAs) that have been found to be associated with promoters in eukaryotes from animals to yeast. After comparing the different classes of such ncRNAs described in various studies, the Review discusses how the models proposed for their origins and their possible functions challenge previous views of the basic transcription process and its regulation.