While just compromising 4% of all skin cancers, malignant melanoma is responsible for the majority of deaths within this tumour group and the incidence is rising worldwide. Melanoma is often caused by mutations due to exposure to ultraviolet radiation. This study reports a recurrent somatic C>T change causing a P131L mutation in the RQCD1 (Required for Cell Differentiation1 Homolog) gene identified through whole exome sequencing of 20 metastatic melanoma cell lines. Screening in 715 additional primary melanomas revealed a prevalence of ~4%. Mutually exclusive mutations of other members of the CCR4-NOT complex were found in ~20% of all subcutaneous melanomas from the TCGA dataset suggesting the complex may play an important role in melanoma biology. Mutant RQCD1 was predicted to bind strongly to HLA-A0201 and HLA-Cw3 MHC1 complexes. Using overlapping peptides to stimulate PBMCs from patients with RQCD1 P131L positive melanomas the immunogenic potential of the mutant vs. wild type RQCD1 was tested. From thirteen patients with mutant RQCD1, an anti-tumor CD8+ response was observed from a single patient’s peripheral blood mononuclear cell population stimulated with mutated peptide compared to wildtype suggesting a neoantigen may be formed. Transient knockdown experiments showed that interference with RQCD1 may increase differentiation in melanoma cell lines. The exact function and role of both, wildtype and mutant RQCD1 in melanoma however, remains elusive and warrants further investigations on a larger scale.