This paper explores the computer modelling aided design and synthesis of β-N-acetylhexosaminidase inhibitors along with their applicability to human disease treatment through biological evaluation in both an enzymatic and cellular setting. We investigated the importance of individual stereocenters, variations in structure–activity relationships along with factors influencing cell penetration. To achieve these goals we modified nitrogen heterocycles in terms of ring size, side chains present and ring nitrogen derivatization. By reducing the inhibitor interactions with the active site down to the essentials we were able to determine that besides the established 2S,3R trans-relationship, the presence and stereochemistry of the CH2OH side chain is of crucial importance for activity. In terms of cellular penetration, N-butyl side chains favour cellar uptake, while hydroxy- and carboxy-group bearing sidechains on the ring nitrogen retarded cellular penetration. Furthermore we show an early proof of principle study that β-N-acetylhexosaminidase inhibitors can be applicable to use in a potential anti-invasive anti-cancer strategy.