Since tumor-draining pulmonary vein blood (PV) is enriched in tumor-secreted products, we hypothesized that it would also be enriched in tumor-derived exosomes, which would be important in the metastasis process. We characterized exosomes from PV of 61 resected non-small cell lung cancer (NSCLC) patients to evaluate its potential as relapse biomarkers. Exosomes were characterized using transmission electron microscopy, western blot and nanoparticle tracking analysis and we examined time to relapse (TTR) and overall survival (OS). Differences between PV and peripheral vein were found. PV was enriched in smaller exosomes than the paired peripheral vein (p = 0.01). Moreover, PV exosome size mode was able to identify relapsed patients (Area under the curve [AUC] = 0.781; 95%CI: 0.6641-0.8978), in whom exosome size was smaller (<112 nm; p < 0.001). The combination of PV exosome size and N (lymph node involvement) showed an AUC of 0.89 (95%CI: 0.80-0.97). Moreover, smaller PV exosome size was associated with shorter TTR (28.3 months vs. not reached, p < 0.001) and OS (43.9 months vs. not reached, p = 0.009). Multivariate analyses identified PV exosome size and stage as independent prognostic markers for TTR and OS. PV exosome size is a promising relapse biomarker after surgery that can add valuable information to clinical variables.