Background: Low-dose computed tomography (LDCT) screening can significantly reduce lung cancer mortality. However, annual screening is limited by low adherence in the USA and still not broadly implemented in Europe. As a result, <10% of lung cancers are detected through existing programs. Thus, there is great need for additional diagnostic modalities, such as a blood test that could be deployed in the primary care setting. Methods: We prospectively recruited 1,189 patients meeting the 2013 USPSTF screening criteria for lung cancer and collected stabilized whole blood. Ultra-deep small RNA sequencing was performed with a method to remove highly abundant erythroid RNAs, opening bandwidth for the detection of less abundant species originating from plasma or the immune cellular compartment. We utilized 100 random data splits to train and evaluate logistic regression classifiers using small RNA expression, discovered an 18-small RNA feature consensus signature (miLung), and validated this in an independent cohort (246 patients). Blood cell sorting and tumor tissue sequencing were performed to deconvolve small RNAs into their source of origin. Results: We generated diagnostic models and report a median ROC AUC of 0.86 (95% CI 0.84-0.86) in the discovery cohort, and generalized performance of 0.84 in the validation cohort. Diagnostic performance increased stage-dependently from 0.73 (95% CI 0.71-0.76) for Stage I to 0.90 (95% CI 0.89-0.90) for Stage IV. We identified a tumor-shed, plasma-bound ribosomal RNA fragment of the L1 stalk as a dominant predictor of lung cancer. The fragment is decreased following surgery with curative intent. In additional experiments, dried blood spot collection and sequencing revealed that small RNA analysis could potentially be conducted via home-sampling. Conclusions: These data suggest the potential of a small RNA-based blood test as a viable alternative to LDCT screening for early detection of smoking-associated lung cancer. Clinical trial information: NCT03452514.