Bread can vary in textural and nutritional attributes based on differences in the bread making process (e.g., flour type, fermentation agent, fermentation time). Four bread recipes (BRs) made with sourdough preferments (BR1, white flour; BR2, whole grain flour) or regular yeast breads (BR3, white flour; BR4, whole grain flour) were evaluated for texture, digestibility, and their effect on the metabolic activity and composition of the gut microbiota using texture profile analysis (TPA) coupled with in vitro upper gastrointestinal (GIT) digestion and colonic fermentation (Colon-on-a-plate™ model), using fecal samples from eight healthy human donors. TPA revealed significantly higher values for hardness, fracturability, gumminess, and chewiness, and significantly lower values for springiness, cohesiveness, and resilience with whole grain versus white breads (all p < 0.001); values for springiness, cohesiveness, and resilience were significantly higher for sourdough versus yeast bread (p < 0.001). Nutrient composition and bioaccessibility were generally comparable between sourdough and yeast bread with similar flours. Following simulation of upper GIT digestion, all BRs demonstrated good digestibility of minerals, carbohydrates, and proteins. Colonic fermentation revealed changes in gut microbiota composition, significant increases in short-chain fatty acids, and a significant decrease in branched short-chain fatty acids with all BRs versus a blank. Overall, new insights into wheat bread digestibility and colonic fermentation were provided, which are important aspects to fully characterize bread nutritional profile and potential.