Non-small cell lung cancer (NSCLC) is the number one cancer killer and its early detection can reduce mortality. Accumulating evidences suggest an etiopathogenic role of microorganisms in lung tumorigenesis. Certain bacteria are found to be associated with NSCLC. Herein we evaluated the potential use of microbiome as biomarkers for the early detection of NSCLC. We used droplet digital PCR to analyze 25 NSCLC-associated bacterial genera in 31 lung tumor and the paired noncancerous lung tissues and sputum of 17 NSCLC patients and ten cancer-free smokers. Of the bacterial genera, four had altered abundances in lung tumor tissues, while five were aberrantly abundant in sputum of NSCLC patients compared with their normal counterparts (all < 0.05). Acidovorax and Veillonella were further developed as a panel of sputum biomarkers that could diagnose lung squamous cell carcinoma (SCC) with 80% sensitivity and 89% specificity. The use of Capnocytophaga as a sputum biomarker identified lung adenocarcinoma (AC) with 72% sensitivity and 85% specificity. The use of Acidovorax as a sputum biomarker had 63% sensitivity and 96% specificity for distinguishing between SCC and AC, the two major types of NSCLC. The sputum biomarkers were further validated for the diagnostic values in a different cohort of 69 NSCLC cases and 79 cancer-free controls. Sputum microbiome might provide noninvasive biomarkers for the early detection and classification of NSCLC.