Escherichia coli O157:H7 is a major foodborne human pathogen causing disease worldwide. Cattle are a major reservoir for this pathogen and those that shed E. coli O157:H7 at >104 CFU/g feces have been termed "super-shedders". A rich microbial community inhabits the mammalian intestinal tract, but it is not known if the structure of this community differs between super-shedder cattle and their non-shedding pen mates. We hypothesized that the super-shedder state is a result of an intestinal dysbiosis of the microbial community and that a "normal" microbiota prevents E. coli O157:H7 from reaching super-shedding levels. To address this question, we applied 454 pyrosequencing of bacterial 16S rRNA genes to characterize fecal bacterial communities from 11 super-shedders and 11 contemporary pen mates negative for E. coli O157:H7. The dataset was analyzed by using five independent clustering methods to minimize potential biases and to increase confidence in the results. Our analyses collectively indicated significant variations in microbiome composition between super-shedding and non-shedding cattle. Super-shedders exhibited higher bacterial richness and diversity than non-shedders. Furthermore, seventy-two operational taxonomic units, mostly belonging to Firmicutes and Bacteroidetes phyla, were identified showing differential abundance between these two groups of cattle. The operational taxonomic unit affiliation provides new insight into bacterial populations that are present in feces arising from super-shedders of E. coli O157:H7.