Johne's disease (JD) is a chronic, intestinal infection of cattle, caused by Mycobacterium avium subsp. paratuberculosis (MAP). It results in granulomatous inflammation of the intestinal lining, leading to malabsorption, diarrhea, and weight loss. Crohn's disease (CD), a chronic, inflammatory gastrointestinal disease of humans, has many clinical and pathologic similarities to JD. Dysbiosis of the enteric microbiota has been demonstrated in CD patients. It is speculated that this dysbiosis may contribute to the intestinal inflammation observed in those patients. The purpose of this study was to investigate the diversity patterns of fecal bacterial populations in cattle infected with MAP, compared to those of uninfected control cattle, using phylogenomic analysis. Fecal samples were selected to include samples from 20 MAP-positive cows; 25 MAP-negative herdmates; and 25 MAP-negative cows from a MAP-free herd. The genomic DNA was extracted; PCR amplified sequenced on a 454 Roche platform, and analyzed using QIIME. Approximately 199,077 reads were analyzed from 70 bacterial communities (average of 2,843 reads/sample). The composition of bacterial communities differed between the 3 treatment groups (P < 0.001; Permanova test). Taxonomic assignment of the operational taxonomic units (OTUs) identified 17 bacterial phyla across all samples. Bacteroidetes and Firmicutes constituted more than 95% of the bacterial population in the negative and exposed groups. In the positive group, lineages of Actinobacteria and Proteobacteria increased and those of Bacteroidetes and Firmicutes decreased (P < 0.001). Actinobacteria was highly abundant (30% of the total bacteria) in the positive group compared to exposed and negative groups (0.1-0.2%). Notably, the genus Arthrobacter was found to predominate Actinobacteria in the positive group. This study indicates that MAP-infected cattle have a different composition of their fecal microbiota than MAP-negative cattle.