Cutaneous melanomas are notorious for their tendency to metastasize. Essential steps in this process are the degradation of basement membranes and remodeling of the extracellular matrix (ECM) by proteolytic enzymes such as matrix metalloproteinases (MMPs), which are regulated by their tissue inhibitors (TIMPs). An MMP expression is not restricted to tumor cells but is also found in stromal cells, indicating that stroma-derived proteases may contribute to melanoma progression. The MMPs have been shown to interact with a broad range of non-matrix proteins including adhesion molecules, growth factors and mediators of angiogenesis and apoptosis. In this review, we evaluate new insights into the interplay of MMPs and their molecular partners in melanoma progression.