beta-N-Acetylhexosaminidases feature so-called wobbling specificity, which means that they cleave substrates both in gluco- and galacto- configurations, with the activity ratio depending on the enzyme source. Here we present the new finding that fungal beta-N-acetylhexosaminidases are able to hydrolyze and transfer 4-deoxy-N-acetylhexosaminides with high yields. This clearly demonstrates that the 4-hydroxy moiety at the substrate pyranose ring is not essential for substrate binding to the enzyme active site, which was also confirmed by molecular docking of the tested compounds into the model of the active site of beta-N-acetylhexosaminidase from Aspergillus oryzae. A set of four 4-deoxy-N-acetylhexosaminides was synthesized and screened against a panel of beta-N-acetylhexosaminidases (extracellular and intracellular) from various sources (fungal, human, animal, plant and bacterial) for hydrolysis. The results of this screening are reported here, as well as the structures of three novel 4'-deoxy-disaccharides prepared by transglycosylation reaction with high yields (52% total disaccharide fraction) using beta-N-acetylhexosaminidase from Talaromyces flavus.