The circulating transcriptome is a valuable source of cancer biomarkers, which, with the exception of microRNAs (miRNAs), remains relatively unexplored. To elucidate which RNAs are present in plasma from melanoma patients and which could be used to distinguish cancer patients from healthy individuals, we used next generation sequencing (NGS), and validation was carried out by qPCR and/or ddPCR. We identified 442 different microRNAs in samples, eleven of which were differentially expressed (p < 0.05). Levels of miR-134-5p and miR-320a-3p were significantly down-regulated (p < 0.001) in melanoma samples (n = 96) compared to healthy controls (n = 28). Differentially expressed protein-encoding mRNA 5′-fragments were enriched for the angiopoietin, p21-activated kinase (PAK), and EIF2 pathways. Levels of ATM1, AMFR, SOS1, and CD109 gene fragments were up-regulated (p < 0.001) in melanoma samples (n = 144) compared to healthy controls (n = 41) (AUC = 0.825). Over 40% of mapped reads were YRNAs, a class of non-coding RNAs that to date has been little explored. Expression levels of RNY3P1, RNY4P1, and RNY4P25 were significantly higher in patients with stage 0 disease than either healthy controls or more advanced stage disease (p < 0.001). In conclusion, we have identified a number of novel RNA biomarkers, which, most importantly, we validated in multi-center retrospective and prospective cohorts, suggesting potential diagnostic use of these RNA species.