Statement of the Problem: Flatulence is a symptom of indigestion and is usually caused by eating certain foods that cause bloating. Humans are not able to digest oligosaccharides with alpha-galactosyl moieties, therefore, the consumption of legumes which naturally have high concentrations of indigestible oligosaccharides, ultimately fermented by the colonic flora and cause to produce gas. The enzyme alpha-galactosidase could break down the terminal alpha-galactosyl moieties from glycolipids, glycoproteins, and oligosaccharides to give low molecular weight products. Thus, using capable alpha-galactosidase-producing probiotics could be suggested to be a safe approach for the reduction of gastrointestinal gas besides other benefits. The aim of this study is the screening of alpha galactosidase-producing probiotics with anti-flatulence potential. Methodology & Theoretical Orientation: Bacterial strains were selected from the Bacterial Culture Collection of Shiraz University of Medical Sciences (BCCS) and screened on MRS plates containing 0.01% bromocresol purple to select alpha-galactosidase-producing bacteria. Alpha galactosidase activity was assayed. For probiotic characterization, all probiotic evaluated tests were done. Findings: Among 121 bacteria, 21 strains produced alpha-galactosidase and defined as probiotics. Lactobacillus acidophilus strain BCCS A49 with 0.6±0.05 U/mL activity and Lactobacillus acidophilus strain BCCS A50 with 0.86±0.04 U/mL activity produced a high yield of alpha-galactosidase. Conclusion & Significance: These strains could be selected to use as therapeutic agents to reduce gastrointestinal gas by replacement with colonic flora, in a safe approach with further studies. Keywords: anti-flatulence, gastrointestinal gas, probiotic, alpha-galactosidase, Lactobacillus.