In this work, focused on possible application of α-L-fucosidases from bacterial sources in the synthesis of α-L-fucosylated glycoconjugates, several nonpathogenic aerobic bacterial strains were screened for α-L-fucosidase activity. Among them Paenibacillus thiaminolyticus was confirmed as a potent producer of enzyme with the ability to cleave the chromogenic substrate p-nitrophenyl α-L-fucopyranoside. The gene encoding α-L-fucosidase was found using the genomic library of P. thiaminolyticus constructed in the cells of Escherichia coli DH5α and sequenced (EMBL database: FN869117, carbohydrate-active enzymes database: Glycosidase family 29). The enzyme was expressed in the form of polyhistidine-tagged protein (51.2 kDa) in Escherichia coli BL21 (DE3) cells, purified using nickel-nitrilotriacetic acid agarose affinity chromatography and characterized using the chromogenic substrate p-nitrophenyl α-L-fucopyranoside (Km = (0.44 ± 0.02) mmol/L, KS = (83 ± 8) mmol/L (substrate inhibition), pHoptimum = 8.2, toptimum = 48°C). By testing the ability of the enzyme to catalyze the transfer of α-L-fucosyl moiety to different types of acceptor molecules, it was confirmed that the enzyme is able to catalyze the formation of α-L-fucosylated p-nitrophenyl glycopyranosides containing α-D-galactopyranosidic, α-D-glucopyranosidic, α-D-mannopyranosidic or α-L-fucopyranosidic moiety. This enzyme is also able to catalyze α-L-fucosylation of aliphatic alcohols of different lenghs of alkyl chain and hydroxyl group positions (methanol, ethanol, 1-propanol, 2-propanol and 1-octanol) and hydroxyl group-containing amino acid derivatives (N-(tert-butoxycarbonyl)-L-serine methyl ester and N-(tert-butoxycarbonyl)-L-threonine methyl ester). These results indicate the possibility of exploiting this enzyme in the synthesis of different types of α-L-fucosylated molecules representing compounds with potential application in biotechnology and the pharmaceutical industry.