Trichostome ciliates are among the most conspicuous protists in the gastrointestinal tract of a large variety of vertebrates. However, little is still known about phylogeny of the trichostome/vertebrate symbiotic systems, evolutionary correlations between trichostome extrinsic traits, and character-dependent diversification of trichostomes. These issues were investigated here, using the relaxed molecular clock technique along with stochastic mapping of character evolution, and binary-state speciation and extinction models. Clock analyses revealed that trichostomes colonized the vertebrate gastrointestinal tract ∼135 Ma, that is, near the paleontological minimum for the split of therian mammals into marsupials and placentals. According to stochastic mapping, the last common ancestor of trichostomes most likely invaded the hindgut of a mammal. Although multiple shifts to fish/amphibian or avian hosts and to the foregut compartments took place during the trichostome phylogeny, only transition to the foregut was recognized as a key innovation responsible for the explosive radiation of ophryoscolecid trichostomes after the Cretaceous/Tertiary boundary, when ungulates began their diversification. Since crown radiations of main trichostome lineages follow those of their mammalian hosts and are in agreement with their historic dispersal routes, the present time-calibrated phylogeny might help to elucidate controversies in the geological and molecular timing of the split between marsupials and placental mammals.