Highly cellulolytic bacterial species such as Ruminococcus flavefaciens are regarded essential for the microbial breakdown of cellulose in the rumen. We have investigated the effect of ruminal dosing of R. flavefaciens strain 8/94-32 during realimentation of starved reindeer (males, n = 3). Microbiome function measured as in situ digestion of cellulose and food pellets (percent DMD; dry matter disappearance) decreased after probiotic dosing. Microbial community analyses (>100,000 16S rDNA gene sequences for 27 samples) demonstrated that ruminal dosing influenced the microbiome structure; reflected by increased phylogenetic distances from background samples (unweighted UniFrac analysis) and reduced species diversity and evenness. Despite the inability to detect strain 8/94-32 post-dosing, the relative abundance of its affiliate family Ruminococcaceae remained consistent throughout the trial, whilst a dominant peak in the genus Prevotella and decline in uncharacterized Bacteroidetes (uBacNR) were observed in treatment samples. No clear relationships were observed between the relative abundance of Ruminococcaceae, Prevotella and uBacNR with cellulose DMD; however, Prevotella (negative) and uBacNR (positive) exhibited relationships with pellet DMD. These unexpected effects of ruminal dosing of a cellulolytic bacterium on digestibility are relevant for other studies on rumen manipulation.