Over the past few decades, RNA has emerged as much more than just an intermediary in biology’s central dogma. RNA is now known to play a variety of catalytic, regulatory and defensive roles in living systems as demonstrated through the discoveries of ribozymes, riboswitches, microRNAs, small interfering RNAs, Piwi-interacting RNAs, small nuclear RNAs, clusters of regularly interspaced short palindromic repeat RNAs and long non-coding RNAs. In contrast to the functional diversity of RNA, the chemical diversity has remained primarily limited to canonical polyribonucleotides, the 5’ cap on mRNAs in eukaryotes, modified nucleotides and 3’-aminoacylated tRNAs. This disparity coupled with the powerful functional properties of small molecule-nucleic acid conjugates led us to speculate that novel small molecule-RNA conjugates existed in modern cells, either as evolutionary fossils or as RNAs whose functions are enabled by the small molecule moieties. We developed and applied a nuclease-based screen coupled with high-resolution liquid chromatography/mass spectrometry analysis to detect novel small molecule-RNA conjugates, broadly and sensitively. We discovered NAD-linked RNA in two types of bacteria and further characterized the small molecule and RNA in Escherichia coli. The NAD modification is found on the 5’ end of RNAs between 30 and 120 nucleotides long, and is surprisingly abundant at around 3,000 copies per cell. Subsequent experiments to characterize further NAD-linked RNA have been undertaken, including sequencing the RNAs to which NAD is attached and elucidating the biological functions of the small molecule-RNA conjugate. The development and application of a screen to detect novel nucleotide modifications that is independent of structure or biological context has the potential to increase our understanding of the functional and chemical diversity of RNA. The discovery and biological characterization of NAD-linked RNA can provide new examples of RNA biology and offer insight into the RNA world.