Arylsulfatase B (ARSB; N-acetylgalactosamine 4-sulfatase) is reduced in several malignancies, but levels in melanoma have not been investigated previously. Experiments were performed in melanoma cell lines to determine ARSB activity and impact on melanoma invasiveness. ARSB activity was reduced ~50% in melanoma cells compared to normal melanocytes. Silencing ARSB significantly increased the mRNA expression of chondroitin sulfate proteoglycan(CSPG)4 and pro-matrix metalloproteinase(MMP)-2, known mediators of melanoma progression. Also, invasiveness and MMP activity increased when ARSB was reduced, and recombinant ARSB inhibited invasiveness and MMP activity. Since the only known function of ARSB is to remove 4-sulfate groups from the N-acetylgalactosamine 4-sulfate residue at the non-reducing end of chondroitin 4-sulfate (C4S) or dermatan sulfate, experiments were performed to determine the transcriptional mechanisms by which expression of CSPG4 and MMP2 increased. Promoter activation of CSPG4 was mediated by reduced binding of galectin-3 to C4S when ARSB activity declined. In contrast, increased pro-MMP2 expression was mediated by increased binding of the non-receptor tyrosine phosphatase SHP2 to C4S. Increased phospho-ERK1,2 resulted from SHP2 inhibition. Combined effects of increased C4S, CSPG4, and MMP2 increased the invasiveness of the melanoma cells, and therapy with recombinant ARSB may inhibit melanoma progression.