Mycobacterium tuberculosis is an important human pathogen, and yet diagnosis remains challenging. Little research has focused on the impact of M. tuberculosis on the gut microbiota, despite the significant immunological and homeostatic functions of the gastrointestinal tract. To determine the effect of M. tuberculosis infection on the gut microbiota, we followed mice from M. tuberculosis aerosol infection until death, using 16S rRNA sequencing. We saw a rapid change in the gut microbiota in response to infection, with all mice showing a loss and then recovery of microbial community diversity, and found that pre-infection samples clustered separately from post-infection samples, using ecological beta-diversity measures. The effect on the fecal microbiota was observed as rapidly as six days following lung infection. Analysis of additional mice infected by a different M. tuberculosis strain corroborated these results, together demonstrating that the mouse gut microbiota significantly changes with M. tuberculosis infection.