Background: Non-small cell lung cancer (NSCLC) frequently presents when surgical intervention is no longer feasible. Despite local treatment with curative intent, patients might experience disease recurrence. In this context, accurate non-invasive biomarkers are urgently needed. We report the results of a pilot study on the diagnostic and prognostic role of circulating tumor cells (CTCs) in operable NSCLC. Methods: Blood samples collected from healthy volunteers (n = 10), nodule-negative high-risk individuals enrolled in a screening program (n = 7), and NSCLC patients (n = 74) before surgery were analyzed (4 mL) for the presence of cells with morphological features of malignancy enriched through the ISET® technology. Results: CTC detection was 60% in patients, while no target cells were found in lung cancer-free donors. We identified single CTCs (sCTC, 46%) and clusters of CTCs and leukocytes (heterotypic clusters, hetCLU, 31%). The prevalence of sCTC (sCTC/4 mL ≥ 2) or the presence of hetCLU predicted the risk of disease recurrence within the cohort of early-stage (I–II, n = 52) or advanced stage cases (III–IVA, n = 22), respectively, while other tumor-related factors did not inform prognosis. Conclusions: Cancer cell hematogenous dissemination occurs frequently in patients with NSCLC without clinical evidence of distant metastases, laying the foundation for the application of cell-based tests in screening programs. CTC subpopulations are fine prognostic classifiers whose clinical validity should be further investigated in larger studies.