To date, the 5-year overall survival rate of 60% for early-stage non-small cell lung cancer (NSCLC) is still unsatisfactory. Therefore, reliable prognostic factors are needed. Growing evidence shows that cancer progression may depend on an interconnection between cancer cells and the surrounding tumor microenvironment; hence, circulating molecules may represent promising markers of cancer recurrence. In order to identify a prognostic score, we performed in-depth high-throughput analyses of plasma circulating markers, including exosomal microRNAs (Exo-miR) and peptides, in 67 radically resected NSCLCs. The miRnome profile selected the Exo-miR-130a-3p as the most overexpressed in relapsed patients. Peptidome analysis identified four progressively more degraded forms of fibrinopeptide A (FpA), which were depleted in progressing patients. Notably, stepwise Cox regression analysis selected Exo-miR-130a-3p and the greatest FpA (2-16) to build a score predictive of recurrence, where high-risk patients had 18 months of median disease-free survival. Moreover, in vitro transfections showed that higher levels of miR-130a-3p lead to a deregulation of pathways involved in metastasis and angiogenesis, including the coagulation process and metalloprotease increase which might be linked to FpA reduction. In conclusion, by integrating circulating markers, the identified risk score may help clinicians predict early-stage NSCLC patients who are more likely to relapse after primary surgery.