Regulation of cell surface molecules by matrix metalloproteinases (MMPs), as well as MMPs-catalyzed degradation of extracellular matrix, is important for tumor invasion and metastasis. Our previous study (Kioi, M., Yamamoto, K., Higashi, S., Koshikawa, N., Fujita, K., and Miyazaki, K. (2003) Oncogene 22, 8662-8670) demonstrated that active matrilysin specifically binds to the surface of colon cancer cells and induces notable cell aggregation due to processing of the cell membrane protein(s). Furthermore, these aggregated cells showed a dramatically enhanced metastatic potential. To elucidate the mechanism of matrilysin-induced cell aggregation, we attempted to identify the matrilysin-binding substance on the cell surface. Here, we demonstrate that cholesterol sulfate on the cell surface is a major matrilysin-binding substance. We found that active matrilysin bound to the cell membrane and cholesterol sulfate incorporated into liposomes with similar affinities. Treatment of colon cancer cells with beta-cyclodextrin significantly reduced not only matrilysin binding to the cell surface but also matrilysin-dependent proteolysis and cell aggregation. Interestingly, replenishment of cholesterol sulfate, but not cholesterol, neutralized the effects of beta-cyclodextrin. Taken together, it is likely that binding of matrilysin to cholesterol sulfate facilitates the matrilysin-catalyzed modulation of cell surface proteins, thus inducing the cancer cell aggregation.