Tumor cells, in particular melanoma cells, can be detected as abnormal self by cytotoxic lymphocytes of the innate and adaptive immune system. Of major importance in this process is the activating lymphocyte receptor NKG2D that in humans binds to MIC and ULBP surface molecules on tumor cells. Expression of NKG2D ligands (NKG2DL) is an early event in malignant transformation, induced by stress-associated and oncogene-driven pathways. Thus NKG2DL expression is considered as an innate barrier against tumor development. However, tumor cells can overcome this barrier by shedding of NKG2DL. Ligand shedding leads to elevated levels of soluble ligands in sera of tumor patients that in case of melanoma are of strong prognostic relevance. Here we review important aspects of NKG2DL expression and regulation in tumor cells with a focus on melanoma, and discuss their clinical relevance and potential in immunotherapy.