Johne's disease (JD) is a chronic gastrointestinal infection of cattle caused by Mycobacterium avium ssp. paratuberculosis (MAP). In the US, more than 68% of dairy herds are infected with MAP, leading to considerable financial losses for producers. We hypothesized that cattle naturally infected with MAP have a reduction in gastrointestinal microbial biodiversity and gastrointestinal dysbiosis may play a role in the pathogenesis of JD. In the present study, fecal samples from 20 naturally infected (positive group); 25 JD-negative herdmates (exposed group); and 25 JD-negative cows from a MAP-free herd (negative group) were obtained from New Bolton Center, JD repository. All fecal samples were processed for genomic DNA and amplified for the V1-V2 regions of the 16S rDNA gene. Sequencing was performed on a 454 Roche Platform and sequences were analyzed using QIIME. Approximately 252,380 reads were analyzed from 70 bacterial communities with an average of 2,843 reads per sample. Approximately 34,606 operational taxonomic units (OTUs) were produced by clustering at 97% sequence similarity. Weighted and unweighted Unifrac distances by principal coordinate analysis showed a substantial difference (P < 0.001; Permanova test) in the bacterial community composition of the positive group verses the exposed and negative groups. Taxonomic assignment of the OTUs identified a total of 18 bacterial phyla across all samples. Across negative and exposed groups, Bacteroidetes and Firmicutes constituted more than 95% of the total bacterial population. However, 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 with <0.1% in exposed and negative groups. Therefore, it is apparent that bacterial communities in exposed and negative groups were homologous whereas significant variation in positive samples was observed. Bacterial diversity in positive group was compromised compared with negative and exposed groups.