Background: The search for non-invasive diagnostic methods of lung cancer (LC) has led to new avenues of research, including the exploration of the exhaled breath. Previous studies have shown that LC can be detected through exhaled-breath analysis. This study evaluated the potential of exhaled-breath analysis for the distinction of early and advanced LC and for control (COPD) and lung cancer patients in an international setting. Methods: Breath samples were taken from untreated lung cancer patients and matching COPD controls. Patients were enrolled in Israel, Colorado and Florida. All samples were analyzed in a central lab (Technion Institute; Haifa, Israel). Analysis was performed by both gold nanoparticle-based Artificial Olfactory System (NaNose) and gas-chromatography linked with mass-spectrometry (GC-MS). Pattern recognition methods were used to analyze the results obtained from GC-MS and NaNose to correlate the results with the clinical data. Results: A total of 358 subjects were enrolled in this study (Israel: 174; Denver: 111; Florida: 73). 213 patients had lung cancer, among 62 early disease and 143 were at advanced stage. 145 patients did not have cancer. In our preliminary sub-analysis, of 80 cancer patients (64 advanced stage) and 31 COPDs subjects: discriminant function analysis of the signals of the sensor array distinguished significantly between control versus early LC (p < 0.0001; accuracy 85.11%), between control and advanced LC (p < 0.0001; 82.11%) and between early and advanced LC (p< 0.0001; 78.75%). Conclusions: In this multi-national pilot study, breath analysis discriminated malignant disease from benign conditions in a high-risk cohort based on LC-related volatile organic compound profiles. Furthermore, it discriminated between early versus advanced disease. These achievements stand in consistency with the requirements of society for rapid and early diagnosis of diseases as a part of therapeutic approach and facilitating rapid treatment. Clinical trial information: NCT01386203.