Bile salt hydrolases (BSHs) are currently being investigated as target enzymes for metabolic regulators in humans and as growth promoters in farm animals. Understanding structural features underlying substrate specificity is necessary for inhibitor design. Here, we used a multidisciplinary workflow including mass spectrometry, mutagenesis, molecular dynamic simulations, machine learning, and crystallography to demonstrate substrate specificity in Lactobacillus salivarius BSH, the most abundant enzyme in human and farm animal intestines. We show the preference of substrates with a taurine head and a dehydroxylated sterol ring for hydrolysis. A regression model that correlates the relative rates of hydrolysis of various substrates in various enzyme mutants with the residue-substrate interaction energies guided the identification of structural determinants of substrate binding and specificity. In addition, we found T208 from another BSH protomer regulating the hydrolysis. The designed workflow can be used for fast and comprehensive characterization of enzymes with a broad range of substrates.