Background: Human milk does not meet the nutritional needs to support optimal growth of very preterm infants during the first weeks of life. Nutrient fortifiers are therefore added to human milk, though these products are suspected to increase gut dysmotility. The objective was to evaluate whether fortification with bovine colostrum (BC) improves bowel habits compared to a conventional fortifier (CF) in very preterm infants. Methods: In an unblinded, randomized study, 242 preterm infants (26–31 weeks of gestation) were randomized to receive BC (BC, Biofiber Damino, Gesten, Denmark) or CF (FM85 PreNAN, Nestlé, Vevey, Switzerland) as a fortifier. Stools (Amsterdam Stool Scale), bowel gas restlessness, stomach appearance score, volume, and frequency of gastric residuals were recorded before each meal until 35 weeks post-menstrual age. Results: As intake of fortifiers increased, stools became harder in both groups (p < 0.01) though less in BC infants (p < 0.05). The incidence of bowel gas restlessness increased with laxative treatments and days of fortification in both groups (p < 0.01), but laxatives were prescribed later in BC infants (p < 0.01). With advancing age, stomach appearance scores improved, but more so in BC infants (p < 0.01). Conclusions: Although there are limitations, a minimally processed, bioactive milk product such as BC induced similar or slightly improved bowel habits in preterm infants.