Thirty two Holstein calves were used to investigate the effects of sodium butyrate (SB), phytogenic compounds (PC; consisting mainly of caraway, liquorice extract, oak bark and vanilla flavour), and egg yolk antibodies (EY) supplementation in milk replacer (MR) containing probiotic bacteria on the counts of total bacteria and selected bacteria in faeces. The calves were fed a mixture of surplus colostrum, transition milk and whole milk for the first 9 days of life. On day 10, they were assigned to one of four treatments (8 calves/ treatment): 1) MR containing probiotic bacteria but no other feed additives (control treatment; CTRL); 2) MR with SB; 3) MR with PC; and 4) MR with EY. On day 14 of the study, total bacteria counts were higher in EY calves, Lactobacillus spp. counts were higher in PC and EY calves, and Bifidobacterium spp. counts were higher in SB, PC and EY calves compared to CTRL calves. Escherichia coli counts were higher in EY calves and tended to be higher in SB calves compared to CTRL. On day 28 of the study, total bacteria counts tended to be lower in PC calves, Lactobacillus spp. counts were higher, while Clostridium perfringens counts were lower in EY calves compared to CTRL calves. It was concluded that the supplementation of SB, PC and EY in MR already containing probiotic bacteria may either increase or reduce the abundance of beneficial (Lactobacillus spp. and Bifidobacterium spp.) but also undesired (E. coli, and C. perfringens) bacteria in calf faeces. Of the investigated feed additives, PC supplementation exerted the most beneficial effect on the composition of faecal bacteria, while EY supplementation can reduce C. perfringens shedding in faeces.