Probiotics are living microorganisms that provide health benefits to their hosts, potentially aiding in the treatment or prevention of various diseases, including diarrhea, irritable bowel syndrome, ulcerative colitis, and Crohn’s disease. Motivated by successful applications of link prediction in medical and biological networks, we applied link prediction to the probiotic-disease network to identify unreported relations. Using data from the Probio database and International Classification of Diseases-10th Revision (ICD-10) resources, we constructed a bipartite graph focused on the relationship between probiotics and diseases. We applied customized link prediction algorithms for this bipartite network, including common neighbors, Jaccard coefficient, and Adamic/Adar ranking formulas. We evaluated the results using Area under the Curve (AUC) and precision metrics. Our analysis revealed that common neighbors outperformed the other methods, with an AUC of 0.96 and precision of 0.6, indicating that basic formulas can predict at least six out of ten probable relations correctly. To support our findings, we conducted an exact search of the top 20 predictions and found six confirming papers on Google Scholar and Science Direct. Evidence suggests that Lactobacillus jensenii may provide prophylactic and therapeutic benefits for gastrointestinal diseases and that Lactobacillus acidophilus may have potential activity against urologic and female genital illnesses. Further investigation of other predictions through additional preclinical and clinical studies is recommended. Future research may focus on deploying more powerful link prediction algorithms to achieve better and more accurate results.