The clinical management of non-small cell lung cancer (NSCLC) would benefit greatly by a test that was able to detect small amounts of NSCLC in the peripheral blood. In this report, we used a novel strategy to enrich tumor cells from the peripheral blood of 24 stage I to IV NSCLC patients and determined expression levels for six cancer-associated genes (lunx, muc1, KS1/4, CEA, CK19, and PSE). Using thresholds established at three standard deviations above the mean observed in 15 normal controls, we observed that lunx (10 of 24, 42%), muc1 (5 of 24, 21%), and CK19 (5 of 24, 21%) were overexpressed in 14 of 24 (58%) peripheral blood samples obtained from NSCLC patients. Patients who overexpressed either KS1/4 (n = 2) or PSE (n = 1) also overexpressed either lunx or muc1. Of patients with presumed curable and resectable stage I to II disease (n = 7), at least one marker was overexpressed in three (43%) patients. In advanced stage III to IV patients (n = 17), at least one marker was overexpressed in 11 patients (65%). These results provide evidence that circulating tumor cells can be detected in NSCLC patients by a high throughput molecular technique. Further studies are needed to determine the clinical relevance of gene overexpression.