Johne’s disease (JD) is a chronic gastrointestinal infection of cattle caused by Mycobacterium avium ssp. paratuberculosis (MAP). We hypothesized that cattle naturally infected with MAP acquire gastrointestinal dysbiosis which may play a role in the pathogenesis of JD. To this end, we compared the fecal microbiomes of 20 naturally infected fecal samples (positive group), 10 JD-negative herd mates (exposed group) and 10 JD-negative cows from a MAP-free herd (negative group). Metagenomic DNA libraries were constructed and sequenced on Ion Torrent platform and assembled using NextGENe (V2) program. Phylogenetic assignments and functional annotations of assembled contigs were performed with RefSeq and COGs database respectively using MG-RAST Server. Bray-Curtis dissimilarity distance based analysis showed significant differences (P < 0.05; PERMANOVA) between positive, exposed and negative groups. Taxonomic annotations revealed the abundance of bacteria at up to 85%. Although the same phylotypes were commonly present among all 3 groups, their relative abundance varied (P < 0.05; Wilcoxon), particularly in the positive group. Notably, Actinobacteria was highly abundant (30% of the total bacteria) in the positive group, whereas it constituted less than 1% in the other groups. Further, only a small proportion of sequences (100 sequences; 0.002%) were detected as MAP sequences in the positive group, but were not detected in the other 2 groups. Functional annotations showed the abundance of metabolism pathways at up to 25% of gene content. Among metabolic pathways, gene sequences associated with energy production, amino acid metabolism, lipid metabolism, mineral metabolism and secondary metabolites biosynthesis were significantly higher (P < 0.05; Wilcoxon) in the MAP positive group compared with the other 2 groups. While elevated lipid pathways in the MAP positive group denotes that MAP relies heavily on lipid-based substrates such as cholesterol for its growth. An increase in other metabolic pathways probably denotes adaptation mechanisms of MAP in the host.