Although Mycobacterium avium subsp. (MAP) has threatened public health and the livestock industry, the current diagnostic tools (e.g., fecal PCR and enzyme-linked immunosorbent assay [ELISA]) for MAP infection have some limitations, such as inconsistent results due to intermittent bacterial shedding or low sensitivity during the early stage of infection. Therefore, this study aimed to develop a novel biomarker focusing on elucidating the gut microbial signature of MAP-positive ruminants, since the clinical signs of MAP infection are closely related to dysbiosis. 16S rRNA-based gut microbial community analysis revealed both a decrease in microbial diversity and the emergence of several distinct taxa following MAP infection. To determine the discriminant taxa diagnostic of MAP infection, machine learning-based feature selection and predictive model construction were applied to taxon abundance data or their transformed derivatives. The selected taxa, such as Clostridioides (formerly Clostridium) difficile, were used to build models using a support vector machine, linear support vector classification, -nearest neighbor, and random forest with 10-fold cross-validation. The receiver operating characteristic-area under the curve (ROC-AUC) analysis of the models revealed their high accuracy, up to approximately 96%. Collectively, taxonomic signatures of cattle gut microbiotas according to MAP infection status could be identified by feature selection tools and applied to establish a predictive model for the infection state. Due to the limitations, such as intermittent bacterial shedding or poor sensitivity, of the current diagnostic tools for Johne's disease, novel biomarkers are urgently needed to aid control of the disease. Here, we explored the fecal microbiota of Johne's disease-affected cattle and tried to discover distinct microbial characteristics which have the potential to be novel noninvasive biomarkers. Through 16S rRNA sequencing and machine learning approaches, a dozen taxa were selected as taxonomic signatures to discriminate the disease state. In addition, when constructing predictive models using relative abundance data of the corresponding taxa, the models showed high accuracy for classification, even including animals with subclinical infection. Thus, our study suggested novel noninvasive microbiological biomarkers that are robustly expressed regardless of subclinical infection and the applicability of machine learning for diagnosis of Johne's disease.