Gut microbiome has become increasingly a rich resource of information for detecting different diseases, such as diabetes and various forms of cancer. Using gut microbiome for Cardiovascular Disease detection represents a potential opportunity that offers a hope of a cheaper, non-invasive, yet reliable screening method. In this paper, we utilize supervised machine learning to build predictive models trained on sets of informative biomarkers drawn from the microbial composition of fecal samples. The predictive model is used to identify patients having an Atherosclerotic Cardiovascular Disease based on fecal samples. Extensive experiments are conducted using ten different machine learning algorithms and four feature selection/engineering settings to evaluate our proposed methodology. Furthermore, we highlight a set of informative microbes (i.e. biomarkers) in the gut microbiome for Cardiovascular Disease screening. Our best predictive model achieves an Area under the curve (AUC) score of 0.926 when Bayes Net is used as the machine learning algorithm and Correlation-based feature selection method is used for feature selection.