Alterations of gut microbiota have been implicated in multiple diseases including cancer. However, the gut microbiota spectrum in lung cancer remains largely unknown. Here we profiled the gut microbiota composition in a discovery cohort containing 42 early-stage lung cancer patients and 65 healthy individuals through the 16S ribosomal RNA (rRNA) gene sequencing analysis. We found that lung cancer patients displayed a significant shift of microbiota composition in contrast to the healthy populations. To identify the optimal microbiota signature for noninvasive diagnosis purpose, we took advantage of Support-Vector Machine (SVM) and found that the predictive model with 13 operational taxonomic unit (OTU)-based biomarkers achieved a high accuracy in lung cancer prediction (area under curve, AUC = 97.6%). This signature performed reasonably well in the validation cohort (AUC = 76.4%), which contained 34 lung cancer patients and 40 healthy individuals. To facilitate potential clinical practice, we further constructed a 'patient discrimination index' (PDI), which largely retained the prediction efficiency in both the discovery cohort (AUC = 92.4%) and the validation cohort (AUC = 67.7%). Together, our study uncovered the microbiota spectrum of lung cancer patients and established the specific gut microbial signature for the potential prediction of the early-stage lung cancer.