Natural Killer (NK) cells recognize and destroy tumors and virus-infected cells in an antibody-independent manner. The regulation of NK cells is mediated by activating and inhibiting receptors on the NK cell surface. One important family of activating receptors is the natural cytotoxicity receptors (NCRs) which include NKp30, NKp44 and NKp46. The NCRs initiate tumor targeting by recognition of heparan sulfate on cancer cells. This study aims to elucidate heparan sulfate structural motifs that are important for NCR binding. Microarray and surface plasmon resonance experiments with a small library of heparan sulfate/heparin oligosaccharides helped to clarify the binding preferences of the three NCRs. We demonstrate that the NCRs interact with highly charged HS/heparin structures, but differ in preferred modification patterns and chain lengths. The affinity of NKp30 and NKp44 for synthetic HS/heparin is approximately one order of magnitude higher than the affinity of NKp46. We further show the relevance of synthetic HS/heparin for the binding of NCRs to tumor cells and for NCR-mediated activation of natural killer cells. In conclusion, NCRs recognize different microdomains on heparan sulfate with different affinities.