The ratio between proteases and their inhibitors is unbalanced in cancer. The cysteine protease inhibitor cystatin C is internalized by some cancer cells, which affects cellular properties. Here we aimed to investigate if uptake of cystatin C and the related inhibitor cystatin E/M occur in melanoma cell lines and to evaluate to what extent the uptake affects the legumain activity that is typically increased in melanoma. First we studied the basic expression, secretion, and intracellular content of all type 2 cystatins as well as expression and activity of their possible target enzymes legumain and cathepsin B in MDA-MB-435S, A375, and C8161 melanoma cells. Legumain activity was measureable in all cell lines, and of the potential legumain inhibitors, cystatin C, E/M, and F, cystatin C was the one mainly produced. All cells internalized cystatin C added to culture media, leading to increased intracellular cystatin C levels by 120-200%. Cystatin E/M was internalized as well but at a modest rate. The effects on intracellular legumain activity were nevertheless pronounced, probably because the cells lacked this inhibitor, and its affinity for legumain is 100-fold higher than that of cystatin C. Likewise, the low-degree uptake resulted in reduced migration and invasion of A375 cells in Matrigel to an extent comparable with the W106F variant of cystatin C with optimal uptake properties and resulting in much higher intracellular levels. Thus, cystatin E/M appears to be a good candidate to efficiently down-regulate the increased legumain activity, possibly important for the malignant phenotype of melanoma cells.