Matrix remodeling and invasion of basement membrane are the major determinants of malignant progression. Matrix degrading enzymes play a pivotal role in this process and have been shown to be regulated at multiple levels. Using high metastatic B16F10 and its invasive variant B16BL6 cells, we previously demonstrated that the expression ofβ1,6 branched N-oligosaccharides promotes cellular adhesion on different matrix components which in turn induces secretion of MMP9. The present investigations report that although the two cell lines do not differ in the expression of uPAR, expression of MT1-MMP is significantly higher on B16BL6 cells. Analysis of the transcripts of tissue inhibitors of matrix metalloproteinases (TIMPs) showed that expression of both TIMP1 and TIMP2 correlates negatively with the invasive potential of cells. CD44 andβ1 integrin, the two important receptors involved in motility, were identified to carryβ1,6 branched N-oligosaccharides in an invasive potential dependent manner. However, their glycosylation status did not appear to influence their surface expression. Although glycosylation on CD44 had no effect, that onβ1 integrin significantly affected association ofβ1 integrin with MT1-MMP. The results thus demonstrate that the cancer cells use multiple mechanisms for degradation of matrix in a controlled manner to couple it with movement for effective invasion.