The aim of this study was to investigate the effectiveness of tablets containing two probiotic Lactobacillus reuteri strains in inhibiting regrowth of salivary mutans streptococci (MS) after full-mouth disinfection (FMD) with chlorhexidine. The null hypothesis was that the levels of MS would not differ in comparison with a placebo protocol. The study population was comprised of 62 young adults (mean age 23 years) with moderate or high counts of salivary MS who volunteered after informed consent. The study was a double-blinded randomized controlled trial with two parallel groups. After a 3-day chlorhexidine regimen, the subjects were randomly assigned to a test group (n = 32) with probiotic lozenges (2/day) or a placebo group (n = 30). The intervention period was 6 weeks, and stimulated whole saliva was collected at baseline and after 1, 6, and 12 weeks. The samples were processed for MS by a chair-side test and DNA-DNA hybridization as an estimate of 19 bacterial strains associated with oral health and disease. There was no significant difference between the groups at inclusion, and FMD reduced the salivary MS levels significantly in both groups. The MS suppression lasted less than 6 weeks and there were no statistical differences in salivary MS regrowth between the test and control groups at any of the follow-ups. Likewise, there were no major differences in the regrowth patterns of the checkerboard panel between the two groups. We conclude that daily oral administration of L. reuteri did not seem to affect or delay the regrowth of salivary MS after FMD with chlorhexidine.