Colorectal cancer risk is associated with diets high in red meat. Heme, the pigment of red meat, induces cytotoxicity of colonic contents and elicits epithelial damage and compensatory hyperproliferation, leading to hyperplasia. Here we explore the possible causal role of the gut microbiota in heme-induced hyperproliferation. To this end, mice were fed a purified control or heme diet (0.5 μmol/g heme) with or without broad-spectrum antibiotics for 14 d. Heme-induced hyperproliferation was shown to depend on the presence of the gut microbiota, because hyperproliferation was completely eliminated by antibiotics, although heme-induced luminal cytotoxicity was sustained in these mice. Colon mucosa transcriptomics revealed that antibiotics block heme-induced differential expression of oncogenes, tumor suppressors, and cell turnover genes, implying that antibiotic treatment prevented the heme-dependent cytotoxic micelles to reach the epithelium. Our results indicate that this occurs because antibiotics reinforce the mucus barrier by eliminating sulfide-producing bacteria and mucin-degrading bacteria (e.g., Akkermansia). Sulfide potently reduces disulfide bonds and can drive mucin denaturation and microbial access to the mucus layer. This reduction results in formation of trisulfides that can be detected in vitro and in vivo. Therefore, trisulfides can serve as a novel marker of colonic mucolysis and thus as a proxy for mucus barrier reduction. In feces, antibiotics drastically decreased trisulfides but increased mucin polymers that can be lysed by sulfide. We conclude that the gut microbiota is required for heme-induced epithelial hyperproliferation and hyperplasia because of the capacity to reduce mucus barrier function.