The faecal microbiota plays a critical role in host health, with alterations in the human faecal microbial composition associated with various conditions, particularly diarrhoeal diseases. However, little is known about microbial changes during cryptosporidiosis, one of the most important diarrhoeal diseases caused by protozoa in cattle. In this study, alterations in the faecal microbiota of neonatal calves as a result of Cryptosporidium parvum infection were investigated on a C. parvum-positive farm. Comparisons were made among groups of C. parvum-infected, rotavirus-infected, and the pathogen-negative calves. A specific increase in the abundance of Fusobacterium was observed in the faecal microbiota of C. parvum-infected animals. Diarrhoea severity increased in accordance with the abundance of C. parvum and Fusobacterium. Moreover, the specific increase of Fusobacterium appeared to be a universal feature of C. parvum infection, since neonatal calves from geographically separated areas showed the same result. These observations indicated that the growth of Fusobacterium may be an important aggravating factor of cryptosporidiosis.