Early blood biomarkers to diagnose acute stroke could drastically reduce treatment delays. We investigated whether circulating small non-coding RNAs can serve as biomarkers to distinguish between acute ischemic stroke (IS), intracerebral hemorrhage (ICH) and stroke mimics (SM). In an ongoing observational cohort study, we performed small RNA-sequencing in plasma obtained from a discovery cohort of 26 patients (9 IS, 8 ICH and 9 SM) presented to the emergency department within 6 h of symptom onset. We validated our results in an independent dataset of 20 IS patients and 20 healthy controls. ICH plasma had the highest abundance of ribosomal and tRNA-derived fragments, while microRNAs were most abundant in plasma of IS patients. Combinations of four to five tRNAs yielded diagnostic accuracies (areas under the receiver operating characteristics curve) up to 0.986 (ICH vs. IS and SM) in the discovery cohort. Validation of the IS and SM models in the independent dataset yielded diagnostic accuracies of 0.870 and 0.885 to distinguish IS from healthy controls. Thus, we identified tRNA-derived fragments as a promising novel class of biomarkers to distinguish between acute IS, ICH and SM, as well as healthy controls.