Patients with advanced metastatic melanoma have poor prognosis and the genetics underlying its pathogenesis are poorly understood. High-throughput sequencing has allowed comprehensive discovery of somatic mutations in cancer samples. Here, on analysis of our whole-genome and whole-exome sequencing data of 29 melanoma samples, we identified several genes that harbor recurrent nonsynonymous mutations. These included MAP3K5 (mitogen-activated protein kinase kinase kinase-5), which in a prevalence screen of 288 melanomas was found to harbor a R256C substitution in 5 cases. All MAP3K5-mutated samples were wild type for BRAF, suggesting a mutual exclusivity for these mutations. Functional analysis of the MAP3K5 R256C mutation revealed attenuation of MKK4 (mitogen-activated protein kinase kinase 4) activation through increased binding of the inhibitory protein thioredoxin (TXN/TRX-1/Trx), resulting in increased proliferation and anchorage-independent growth of melanoma cells. This mutation represents a potential target for the design of new therapies to treat melanoma.