Dietary pulses, including lentils, are protein-rich plant foods that are enriched in intestinal health-promoting bioactives, such as non-digestible carbohydrates and phenolic compounds. The aim of this study was to investigate the effect of diets supplemented with cooked red lentils on the colonic microenvironment (microbiota composition and activity and epithelial barrier integrity and function). C57Bl/6 male mice were fed one of five diets: a control basal diet (BD), a BD-supplemented diet with 5, 10 or 20% cooked red lentils (by weight), or a BD-supplemented diet with 0.7% pectin (equivalent soluble fiber level as found in the 20% lentil diet). Red lentil supplementation resulted in increased: (1) fecal microbiota α-diversity; (2) abundance of short-chain fatty acid (SCFA)-producing bacteria (e.g., Prevotella, Roseburia and Dorea spp.); (3) concentrations of fecal SCFAs; (4) mRNA expression of SCFA receptors (G-protein-coupled receptors (GPR 41 and 43) and tight/adherens junction proteins (Zona Occulden-1 (ZO-1), Claudin-2, E-cadherin). Overall, 20% lentil had the greatest impact on colon health outcomes, which were in part explained by a change in the soluble and insoluble fiber profile of the diet. These results support recent public health recommendations to increase consumption of plant-based protein foods for improved health, in particular intestinal health.