Abstract Background Differences in HLA allele frequencies between the diseased and healthy populations may signify efficient immune responses, a notion that has been successfully tested for infectious diseases or for association with genetic elements involved in a distinct type of immunity. This retrospective study is intended to detect differences in MHC class I carrier frequencies of advanced melanoma patients compared to healthy bone marrow donors. Methods The HLA-A and -B carrier frequencies of 748 stage IV melanoma patients retrieved from serotyping at 6 different centers in Germany were compared using a chi-square test to 13,386 fully HLA typed bone marrow donors registered in the German national bone marrow donor registry. Results The comparison of HLA carrier frequencies in advanced cancer patients with healthy bone marrow donors revealed a significant decrease in HLA-B8 carrier frequencies, which was also apparent in patients with advanced disease compared to patients with loco-regional disease. Conclusion The data suggest that protective immune responses restricted to distinct MHC class I molecules may be operational in a subset of melanoma patients, which is the prerequisite for a large scale screen for the corresponding epitopes. Alternatively, the known association of the ancestral haplotype HLA-A1, -B8 and -DR3 with genetic elements such as distinct TNF-α alleles might have a protective effect on disease progression. In any case, identification of the cause of protection within this patient subset might lead to a significant improvement in the efficacy of current immunotherapeutic approaches.