Antitumor cytotoxicity of NK cells and T cells expressing NK-associated receptors is regulated by interaction between their cell surface killer immunoglobulin-like receptors (KIRs) and CD94/NKG2 heterodimers with MHC class I ligands on target cells. To test the hypothesis that KIR and/or HLA polymorphisms, and KIR/HLA combinations could contribute to the tumorigenesis, association studies were performed in 50 patients with malignant melanoma (MM) in different stages of disease and 54 controls. Our data showed that the frequency of inhibitory and activating KIR genes and KIR genotypes did not differ significantly between healthy individuals and melanoma patients. HLA haplotype distribution showed statistically significant increased frequencies of A*01-B*35-Cw*04 (0.069 vs 0.000; pc < 0.05; OR = 19.9), A*01-B*08-DRB1*03 (0.079 vs 0.019; pc < 0.05; OR = 4.5), and A*24-B*40-DRB1*11 (0.026 vs 0.000; pc < 0.05; OR = 7.1) in melanoma patients compared with healthy controls. Individuals homozygous for group 2 HLA-C ligands were less frequent in the patient group compared with the control cohort (12% vs 31.5%; p < 0.017). In addition, we observed an increased frequency (88.0% vs 68.5%; p = 0.017; OR = 2.80) of KIR2DL2/2DL3 in combination with their group 1 HLA-C ligands, while the presence of these KIRs in the absence of the putative ligands was decreased (12.0% vs 31.5%; p = 0.017) in the patient group. Furthermore, an increased frequency of activating KIR2DS1 in the absence of the putative HLA-C(Lys80) ligands was found in melanoma patients (16.0% vs 9.2%). In contrast, KIR2DS2 was absent in patients more often (38.0% vs 25.9%) when the presumptive HLA-C(Asn80) ligands were present. A slightly higher incidence of KIR3DL1 in combination with the less effective Bw4(Thr80) ligands was seen in patients with primary (20.8%) compared with metastatic (4.2%) disease. The data obtained in this study imply that there may not be a direct association between KIR gene content in the genome and the presence of malignant melanoma, or melanoma progression. However, some HLA haplotypes could be predisposing to MM in the Bulgarian population. Furthermore, distinct KIR/HLA ligand combinations may be relevant to the development of malignancy whereby inhibition overrides activation of NK cells and T cells expressing NK-associated receptors, which in turn might facilitate tumor escape and progression.