Major Depressive Disorder (MDD), commonly known as Depression, is a mood disorder characterized by persistent feelings of sadness or disinterest. Given the increasing rates of depression, a pressing demand exists for efficient, cost-effective, and accessible methods of depression detection. Traditional psychiatric diagnoses can be time-consuming, costly, and inaccessible for a large portion of the population given their health insurance/plan. In this study, we utilize machine learning to construct a predictive model built on gut microbiome data for the purpose of depression screening. A key part of the pipeline is the use of feature selection/engineering methods for optimization of the feature space as well as the identification of biomarkers. Our experiments show promising results for depression screening using gut microbiome data. We achieve area under ROC score of 0.991, when using Bagging Naive Bayes model with CFS selection method. Furthermore, we identify potential discriminatory and informative biomarkers associated with MDD.