Microbes are residents in a number of body sites, including the oral and nasal cavities, which are connected to the lung via the pharynx. The associations between oral diseases and increased risk of lung cancer have been reported in previous prospective studies. In this study, we measured variations of salivary microbiota and evaluated their potential association with lung cancer, including squamous cell carcinoma (SCC) and adenocarcinoma (AC). A three-phase study was performed: First, we investigated the salivary microbiota from 20 lung cancer patients (10 SCC and 10 AC) and control subjects (n=10) using a deep sequencing analysis. Salivary Capnocytophaga, Selenomonas, Veillonella and Neisseria were found to be significantly altered in patients with SCC and AC when compared to that in control subjects. Second, we confirmed the significant changes of Capnocytophaga, Veillonella and Neisseria in the same lung cancer patients using quantitative PCR (qPCR). Finally, these bacterial species were further validated on new patient/control cohorts (n=56) with qPCR. The combination of two bacterial biomarkers, Capnocytophaga and Veillonella, yielded a receiver operating characteristic (ROC) value of 0.86 with an 84.6% sensitivity and 86.7% specificity in distinguishing patients with SCC from control subjects and a ROC value of 0.80 with a 78.6% sensitivity and 80.0% specificity in distinguishing patients with AC from control subjects. In conclusion, we have for the first time demonstrated the association of saliva microbiota with lung cancer. Particularly, the combination of the 16S sequencing discovery with qPCR validation studies revealed that the levels of Capnocytophaga and Veillonella were significantly higher in the saliva from lung cancer patients, which may serve as potential biomarkers for the disease detection/classification.