Background During the last decade, the scientific community has begun to investigate the composition and role of gut microbiota in normal health and disease. These studies have provided crucial information on the relationship between gut microflora composition and intestinal parasitic infection, and have demonstrated that many enteric pathogen infections are associated with altered gut microflora composition. In this study, we investigated the effects of Cryptosporidium parvum infection (zoonotic protozoan affecting a large range of vertebrates) on both qualitative and quantitative composition of gut microbiota in a CD-1 neonatal mouse model. Methods 5-day-old neonate mice were experimentally infected with 105Cryptosporidium parvum Iowa oocysts by oesophageal gavage. The intestinal microbiota of both infected (Cp+) and uninfected (Cp−) mice groups was examined by high-throughput sequencing of the bacterial 16S rDNA gene V3–V4 hypervariable region. Results The most consistent change in the microbiota composition of Cp+ mice was the increased proportion of bacterial communities belonging to the Phylum Bacteroidetes. In contrast, the microbiota of Cp− mice was associated with increased proportions of several Firmicutes and Actinobacteria phyla members. Conclusion For the first time, our study provides evidence of an association between cryptosporidial infection and gut dysbiosis, thus contributing valuable knowledge to the as-yet little-explored field of Cryptosporidium–microbiota interactions in a neonatal mouse model.