Melanoma is the most aggressive skin cancer once metastasis begins; therefore, it is important to characterize the molecular players involved in melanoma dissemination. The chemokine receptor CXCR4 and the membrane-bound metalloproteinase MT1-MMP are expressed on melanoma cells and represent candidate molecules for the control of metastasis. Using human melanoma transfectants that either overexpress or silence CXCR4 or MT1-MMP, or that have a combination of overexpression and interference of these proteins, we show that CXCR4 and MT1-MMP coordinate their activities at different steps along melanoma cell metastasis into the lungs. Results from in vivo xenograft mouse models of melanoma lung colonization and mice survival and short-term, homing nested polymerase chain reaction experiments from lung samples indicated that CXCR4 is required at early phases of melanoma cell arrival in the lungs. In contrast, MT1-MMP is not needed for these initial steps but promotes subsequent invasion and dissemination of the tumor with CXCR4. Investigation of potential cross talk between CXCR4 and MT1-MMP revealed that MT1-MMP accumulates intracellularly after melanoma cell stimulation with the CXCR4 ligand CXCL12, and that this process involves the activation of the Rac-Erk1/2 pathway. Subsequent to cell contact with specific basement membrane proteins, MT1-MMP redistributes to the cell membrane in a phosphatidylinositol 3-kinase-dependent manner. These results suggest that combination therapies that target CXCR4 and MT1-MMP should improve the limitations of the current therapies for metastatic melanoma.