An integrated in vitro and in silico approach was applied to evaluate the potency of hydroxylated polybrominated diphenyl ethers (OH-PBDEs) and spongiadioxins (OH-PBDDs) isolated from Dysidea sponges on the activity of the recombinant α-d-galactosidase of the GH36 family. It was revealed for the first time that all compounds rapidly and apparently irreversibly inhibited the bacterial α-d-galactosidase. The structure-activity relationship study in the series of OH-PBDEs showed that the presence of an additional hydroxyl group in 5 significantly enhanced the potency (IC50 4.26 μM); the increase of bromination in compounds from 1 to 3 increased their potency (IC50 41.8, 36.0, and 16.0 μM, respectively); the presence of a methoxy group decreased the potency (4, IC50 60.5 μM). Spongiadioxins 6, 7, and 8 (IC50 16.6, 33.1, and 28.6 μM, respectively) exhibited inhibitory action comparable to that of monohydroxylated diphenyl ethers 1-3. Docking analysis revealed that all compounds bind in a pocket close to the catalytic amino acid residues. Molecular docking detected significant compound-enzyme interactions in the binding sites of α-d-galactosidase. Superimposition of the enzyme-substrate and the enzyme-inhibitor complexes showed that their binding sites overlap.