Purpose: This randomised controlled study evaluated the effectiveness of an oral probiotic, Streptococcus salivarius M18 (SsM18), in children with black stains (BSs) in order to counteract their reformation. Materials and Methods: Fifty-eight children (aged 4–10 years) presenting with BSs were enrolled. They were randomly divided into two groups: group A (n = 29) included children who were given the test product containing SsM18 once a day for 3 months; group B (n = 29) included children who did not receive any treatment. Before beginning the study, all the children underwent professional removal of BSs. The assessment of BSs was done after 3 months (T1) and after 6 months (T2). Results: Four patients (1 belonging to group A and 3 to group B) were excluded from the study because they started antibiotic therapy. After 3 months (T1), BSs were detected in 6 of the 28 children (21.2%) from group A and in 13 out of the 26 (50%) children from group B (p < 0.05). After 6 months (T2), BSs were detected in 9 out of the 28 (32.1%) children from group A and in 14 of the 26 (53.8%) children from group B (p > 0.05). Conclusions: BSs formation in children could be prevented by administering S. salivarius M18.