Spontaneous melanoma phenotype switching is controlled by unknown environmental factors and may determine melanoma outcome and responsiveness to anticancer therapy. We show that Orai1 and STIM2 are highly expressed and control store-operated Ca2+ entry in human melanoma. Lower extracellular Ca2+ or silencing of Orai1/STIM2 caused a decrease in intracellular Ca2+, which correlated with enhanced proliferation and increased expression of microphthalmia-associated transcription factor, a marker for proliferative melanoma phenotype. In contrast, the invasive and migratory potential of melanoma cells was reduced upon silencing of Orai1 and/or STIM2. Accordingly, markers for a non-proliferative, tumor-maintaining phenotype such as JARID1B and Brn2 decreased. Immunohistochemical staining of primary melanomas and lymph node metastases revealed a heterogeneous distribution of Orai1 and STIM2 with elevated expression in the invasive rim of the tumor. In summary, our results support a dynamic model in which Orai1 and STIM2 inversely control melanoma growth and invasion. Pharmacological tuning of Orai1 and particularly STIM2 might thus prevent metastatic spread and render melanomas more susceptible to conventional therapy.