Several membrane-bound molecules expressed at the surface of tumor cells have been shown to be released in a soluble form, thereby affecting cell-cell interactions by reduction of ligand densities. Moreover, since the binding domain of the soluble molecules often remains functional, proteolytic cleavage can also reduce the recognition of tumor cells by effector cells bearing the corresponding receptor. Proteolytic cleavage of cell adhesion molecules (CAMs) at the surface of stromal cells, most notably at the surface of vascular endothelial cells, can also limit the recruitment of effector cells at tumor sites. It is noteworthy that, in most cases, the signals that regulate the expression of extracellular proteases are mediated by the same adhesion molecules than those that are targeted by the proteases, suggesting that there is an intimate relationship between extracellular proteases and cell surface adhesion molecules. In this review, we will discuss the functional relationship between CAMs and proteases and how this may lead to tumor evasion.