Lung adenocarcinoma (LUAD) is a global health challenge that urgently requires more accessible and non-invasive screening methods. Traditional diagnostic approaches, such as computed tomography (CT) or biopsies, are effective but can be costly, resource-intensive, and carry associated risks. This study leverages gut microbiome data and machine learning (ML) techniques to develop a non-invasive pre-screening tool for LUAD that can help identify when traditional diagnostic testing is warranted. Using a dataset of 107 fecal samples (43 LUAD and 64 healthy controls), we explored the performance of 9 ML algorithms and 5 distinct feature sets: one baseline set, three generated through feature selection methods, and one created using a feature engineering approach, to identify informative microbial biomarkers and construct accurate classification models. Our results show that feature selection and engineering significantly enhances model performance in comparison to the baseline set. In particular, a Random Forest model combined with Correlation-based Feature Selection (CFS) achieved an Area Under the Curve (AUC) of 0.9967. Furthermore, key taxa, including Prevotella, Coprococcus, Phascolarctobacterium, Bilophila, Blautia, Enterococcus, and Bacteroides, emerged as potential biomarkers. These findings align with previous studies, reinforce the importance of gut microbiota in LUAD, and suggest a promising direction for non-invasive and cost-effective screening methods.