Restraint stress (RS) can induce male reproductive deficits by activating the hypothalamic-pituitary-adrenal (HPA) axis and causing oxidative stress. Previous studies have shown that probiotics can alleviate neurological and metabolic disorders induced by stress. However, the effects of probiotics on RS-induced reproductive deficits have not been fully elucidated. This study aimed to investigate whether Lactobacillus rhamnosus NCDC-610 (Probiotic-1) and Lactobacillus fermentum NCDC-400 (Probiotic-2) with prebiotic (fructooligosaccharides (FOS)) could prevent RS-induced reproductive deficits. C57BL6/J mice were subjected to RS for four hours daily before oral administration of probiotics (4 × 109 CFU per mice) either separately or concurrently with FOS. The results showed that oral administration of Probiotic-1 and Probiotic-2 protected against RS-induced sperm deficits, including sperm count, motility, morphology, and histopathology of testes, and improved intestinal health. Furthermore, Probiotic-1 and Probiotic-2 prevented RS-induced changes in testosterone levels by up-regulating the expressions of steroidogenic acute regulatory protein (StAR), cytochrome P450 side-chain cleavage enzyme (P450scc), and 17β-hydroxysteroid dehydrogenase (17βHSD) in the testes. Additionally, Probiotic-1 and Probiotic-2 increased the activities of catalase and superoxide dismutase and reduced the fold change of interleukin-6 (IL-6), interleukin-10 (IL-10), and tumor necrosis factor-alpha (TNF-α), indicating a protective effect against RS-induced oxidative stress. Oral administration of Probiotic-1 and Probiotic-2, either separately or concurrently with FOS (probiotic dose of 4 × 109 CFU per mice and prebiotic 5% w/v), prevented RS-induced activation of the HPA axis and improved male fertility. These findings suggest that L. rhamnosus NCDC-610 and L. fermentum NCDC-400 are safe and effective probiotics for mitigating stress-induced male reproductive deficits.