The effects of at least some probiotics are restricted to live, metabolically active bacteria at their site of action. Colonization of and persistence in the gastrointestinal tract is thus contributing to the beneficial effects of these strains. In the present study, colonization of an anti-inflammatory Bifidobacterium bifidum strain was studied in C57BL/6J mice under germ-free (GF) and specific pathogen-free (SPF) conditions as well as during dextran sulfate sodium (DSS)-induced colitis. B. bifidum S17/pMGC was unable to stably colonize C57BL/6J mice under SPF conditions. Mono-association of GF mice by three doses on consecutive days led to long-term, stable detection of up to 109 colony forming units (CFU) of B. bifidum S17/pMGC per g feces. This stable population was rapidly outcompeted upon transfer of mono-associated animals to SPF conditions. A B. animalis strain was isolated from the microbiota of these re-conventionalized mice. This B. animalis strain displayed significantly higher adhesion to murine CMT-93 intestinal epithelial cells (IECs) than to human Caco-2 IECs (p = 0.018). Conversely, B. bifidum S17/pMGC, i.e., a strain of human origin, adhered at significantly higher levels to human compared to murine IECs (p < 0.001). Disturbance of the gut ecology and induction of colitis by DSS-treatment did not promote colonization of the murine gastrointestinal tract (GIT) by B. bifidum S17/pMGC. Despite its poor colonization of the mouse GIT, B. bifidum S17/pMGC displayed a protective effect on DSS-induced colitis when administered as viable bacteria but not as UV-inactivated preparation. Collectively, these results suggest a selective disadvantage of B. bifidum S17/pMGC in the competition with the normal murine microbiota and an anti-inflammatory effect that requires live, metabolically active bacteria.