Tumor cell adhesion and proteolysis of the extracellular matrix proteins surrounding the cells are tightly linked processes in tumor invasion. In this study, we sought to identify components of the cell surface of a vertical growth phase melanoma cell line, WM1341D, that mediate invasive cellular behavior. We determined by antisense inhibition that melanoma chondroitin sulfate proteoglycan (MCSP) and membrane-type 3 matrix metalloproteinase (MT3-MMP) expressed on WM1341D are required for invasion of type I collagen and degradation of type I gelatin. MT3-MMP co-immunoprecipitated with MCSP in WM1341D melanoma cells cultured on type I collagen or laminin. The association between MT3-MMP and MCSP was largely disrupted by removing chondroitin sulfate glycosaminoglycan (CS) from the cell surface, suggesting CS could mediate the association between the two cell surface core proteins. Recombinant MT3-MMP and MT3-MMP from whole cell lysates of WM1341D cells were specifically eluted from CS- conjugated affinity columns. The results indicate that MT3-MMP possesses the potential to promote melanoma invasion and proteolysis and that the formation of a complex between MT3-MMP and MCSP may be a crucial step in activating these processes.