Lung cancer is the leading cause of cancer deaths in worldwide. There are many challenges to detect early stage lung cancer in accurate, inexpensive, and non-invasive ways. In this study, we have designed, fabricated, and characterized a sensor system as a novel lung cancer diagnosis tool. In order to investigate the clinical feasibility of the system to detect early stage lung cancer, exhaled breath was collected from 37 patients with non-small cell lung cancer (81.1% of stage I and II) and 48 healthy controls. Three types of samples were collected from each patient; 1) before lung cancer surgery, 2) the first outpatient clinic visit after surgery, and 3) the second outpatient clinic visit after surgery. The sampling schedule from the healthy controls matched that of the lung cancer patients. The volatile organic compounds (VOCs) in the exhaled breath were analyzed by the sensor system. The sensor system consisted of an array of seven metal oxide gas sensors, a gas flow controlling module, heating module, gas adsorption-desorption module and classifiers for data analysis. The result obtained for the first set of samples, using a multilayer perceptron (MLP) for classification indicated a total accuracy of 75.0% with 79.0% of sensitivity and 72.0% of specificity. 93.5% of healthy controls showed nearly unchanged data from the first to the third samples, while 45.2% of lung cancer patients showed definitely changed data from the first to the third samples when analyzed the projection results of original data onto the selected principal components (PCs) obtained from principal component analysis (PCA). The study showed that VOCs in exhaled breath potentially discriminated mostly early stage lung cancer patients before the surgery from healthy volunteers with our sensor system. Furthermore, the prognosis of the lung cancer patients after surgery would be predicted by this system. These results suggest that breath analysis may develop as a novel diagnostic tool for early lung cancer.