Abstract Background High activity of cysteine proteases such as legumain and the cathepsins have been shown to facilitate growth and invasion of a variety of tumor types. In breast cancer, several recent studies have indicated that loss of the cysteine protease inhibitor cystatin E/M leads to increased growth and metastasis. Although cystatin E/M is normally expressed in the skin, its role in cysteine protease regulation and progression of malignant melanoma has not been studied. Methods A panel of various non-melanoma and melanoma cell lines was used. Cystatin E/M and C were analyzed in cell media by immunoblotting and ELISA. Legumain, cathepsin B and L were analyzed in cell lysates by immunoblotting and their enzymatic activities were analyzed by peptide substrates. Two melanoma cell lines lacking detectable secretion of cystatin E/M were transfected with a cystatin E/M expression plasmid (pCST6), and migration and invasiveness were studied by a Matrigel invasion assay. Results Cystatin E/M was undetectable in media from all established melanoma cell lines examined, whereas strong immunobands were detected in two of five primary melanoma lines and in two of six lines derived from patients with metastatic disease. Among the four melanoma lines secreting cystatin E/M, the glycosylated form (17 kD) was predominant compared to the non-glycosylated form (14 kD). Legumain, cathepsin B and L were expressed and active in most of the cell lines, although at low levels in the melanomas expressing cystatin E/M. In the melanoma lines where cystatin E/M was secreted, cystatin C was generally absent or expressed at a very low level. When melanoma cells lacking secretion of cystatin E/M were transfected with pCST6, their intracellular legumain activity was significantly inhibited. In contrast, cathepsin B activity was not affected. Furthermore, invasion was suppressed in cystatin E/M over-expressing melanoma cell lines as measured by the transwell Matrigel assay. Conclusions These results suggest that the level of cystatin E/M regulates legumain activity and hence the invasive potential of human melanoma cells.