In mammals, multiple physiological, metabolic, and behavioral processes are subject to circadian rhythms, adapting to changing light in the environment. Here we analyzed circadian rhythms in the fecal microbiota of mice using deep sequencing, and found that the absolute amount of fecal bacteria and the abundance of Bacteroidetes exhibited circadian rhythmicity, which was more pronounced in female mice. Disruption of the host circadian clock by deletion of Bmal1, a gene encoding a core molecular clock component, abolished rhythmicity in the fecal microbiota composition in both genders. Bmal1 deletion also induced alterations in bacterial abundances in feces, with differential effects based on sex. Thus, although host behavior, such as time of feeding, is of recognized importance, here we show that sex interacts with the host circadian clock, and they collectively shape the circadian rhythmicity and composition of the fecal microbiota in mice.