Microbial dysbiosis has emerged as a modulator of oncogenesis and response to therapy, particularly in lung cancer. Here, we investigate the evolution of the gut and lung microbiomes following exposure to a tobacco carcinogen. We performed 16S rRNA-Seq of fecal and lung samples collected prior to and at several timepoints following (nicotine-specific nitrosamine ketone/NNK) exposure in Gprc5a^−/− mice that were previously shown to exhibit accelerated lung adenocarcinoma (LUAD) development following NNK exposure. We found significant progressive changes in human-relevant gut and lung microbiome members (e.g., Odoribacter, Alistipes, Akkermansia, and Ruminococus) that are closely associated with the phenotypic development of LUAD and immunotherapeutic response in human lung cancer patients. These changes were associated with decreased short-chain fatty acids (propionic acid and butyric acid) following exposure to NNK. We next sought to study the impact of Lcn2 expression, a bacterial growth inhibitor, given our previous findings on its protective role in LUAD development. Indeed, we found that the loss of Lcn2 was associated with widespread gut and lung microbiome changes at all timepoints, distinct from those observed in our Gprc5a^−/− mouse model, including a decrease in abundance and diversity. Our overall findings apprise novel cues implicating microbial phenotypes in the development of tobacco-associated LUAD.