(1) Background: Cold atmospheric plasma (CAP) is ionized gas near room temperature. The anti-cancer effects of CAP were confirmed for several cancer types and were attributed to CAP-induced reactive species. However, the mode of action of CAP is still not well understood. (2) Methods: Changes in cytoplasmic Ca2+ level after CAP treatment of malignant melanoma cells were analyzed via the intracellular Ca2+ indicator fura-2 AM. CAP-produced reactive species were determined by fluorescence spectroscopic and protein nitration by Western Blot analysis. (3) Results: CAP caused a strong acidification of water and solutions that were buffered with the so-called Good buffers, while phosphate-buffered solutions with higher buffer capacity showed minor pH reductions. The CAP-induced Ca2+ influx in melanoma cells was stronger in acidic pH than in physiological conditions. NO formation that is induced by CAP was dose- and pH-dependent and CAP-treated solutions only caused protein nitration in cells under acidic conditions. (4) Conclusions: We describe the impact of CAP-induced acidification on the anti-cancer effects of CAP. A synergistic effect of CAP-induced ROS, RNS, and acidic conditions affected the intracellular Ca2+ level of melanoma cells. As the microenvironment of tumors is often acidic, further acidification might be one reason for the specific anti-cancer effects of CAP.