Lung cancer (LC) is the most prevalent cancer worldwide, and responsible for over 1.3 million deaths each year. Currently, LC has a low five year survival rates relative to other cancers, and thus, novel methods to screen for and diagnose malignancies are necessary to improve patient outcomes. Here, we report on a pilot-sized study to evaluate the potential of the sputum microbiome as a source of non-invasive bacterial biomarkers for lung cancer status and stage. Spontaneous sputum samples were collected from ten patients referred with possible LC, of which four were eventually diagnosed with LC (LC+), and six had no LC after one year (LC-). Of the seven bacterial species found in all samples, Streptococcus viridans was significantly higher in LC+ samples. Seven further bacterial species were found only in LC-, and 16 were found only in samples from LC+. Additional taxonomic differences were identified in regards to significant fold changes between LC+ and LC-cases, with five species having significantly higher abundances in LC+, with Granulicatella adiacens showing the highest level of abundance change. Functional differences, evident through significant fold changes, included polyamine metabolism and iron siderophore receptors. G. adiacens abundance was correlated with six other bacterial species, namely Enterococcus sp. 130, Streptococcus intermedius, Escherichia coli, S. viridans, Acinetobacter junii, and Streptococcus sp. 6, in LC+ samples only, which could also be related to LC stage. Spontaneous sputum appears to be a viable source of bacterial biomarkers which may have utility as biomarkers for LC status and stage.