Matrix metalloproteinases (MMPs) are zinc-dependent endopeptidases that cleave and degrade a wide spectrum of extracellular matrix components. By enhancing turnover of extracellular matrix, MMP activity is also known to play a key role in tumor cell invasion. Because extracellular protease activity requires efficient release of these proteases to the cellular surface, we investigated storage, transport, and exocytosis of MMP-2 and MMP-9 in human melanoma cells using immunofluorescence, electrical, and biochemical techniques. Immunolabeling of melanoma cells with antibodies specific for MMP-2 and MMP-9 led to the identification of two distinct populations of small cytoplasmatic vesicles containing MMP-2 or MMP-9, respectively. In combination with alpha-tubulin-specific antibodies, both vesicle populations were found to be aligned along the microtubular network. Moreover, the molecular motor protein kinesin is shown to be localized on most of these vesicles, providing evidence that the identified vesicles are actively propelled along microtubules toward the plasma membrane. The functional relevance of these findings is demonstrated using low dosage (5.9 nmol/L) of paclitaxel to affect the microtubular function of melanoma cells. Although cell proliferation is not altered, paclitaxel treatment impairs secretion of MMP-2/MMP-9 and significantly reduces invasive activity in our new cell invasion assay. In conclusion, we demonstrate in melanoma cells that microtubule-dependent traffic of MMP-containing vesicles and exocytosis are critical steps for invasive behavior and therefore are potential targets for specific antitumor drugs.