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 melanomas. Screening in 715 additional primary melanomas revealed a prevalence of ~4%. This represents the first reported recurrent mutation in a member of the CCR4-NOT complex in cancer. Compared to tumors without the mutation, the P131L mutant positive tumors were associated with increased thickness (p = 0.02), head and neck (p = 0.009) and upper limb (p = 0.03) location, lentigo maligna melanoma subtype (p = 0.02) and BRAF V600K (p = 0.04) but not V600E or NRAS codon 61 mutations. There was no association with nodal disease (p = 0.3). Mutually exclusive mutations of other members of the CCR4-NOT complex were found in ~20% of the TCGA melanoma 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. From thirteen patients with mutant RQCD1, an anti-tumor CD8⁺ T cell response was observed from a single patient's peripheral blood mononuclear cell population stimulated with mutated peptide compared to wildtype indicating a neoantigen may be formed.