Malignant melanomas are characterized by their high propensity to invade and metastasize, but the molecular mechanisms of these traits have remained elusive. Our DNA microarray analyses of benign nevi and melanoma tissue specimens revealed that the genes encoding extracellular matrix proteins tenascin-C (TN-C), fibronectin (FN), and procollagen-I (PCOL-I) are highly upregulated in invasive and metastatic melanomas. The expression and distribution of these proteins were further studied by immunohistochemistry in benign nevi, radially and vertically growing melanomas, sentinel node micrometastases, and macrometastases. TN-C was increased in all invasive tumours and metastases, especially at invasion fronts, but not in benign nevi or non-invasive melanomas. Significantly, the intensity of TN-C staining correlated with metastasis to sentinel lymph nodes, better than tumour thickness (Breslow). Moreover, TN-C, FN, and PCOL-I appeared to co-localize in the tumours and form tubular meshworks and channels ensheathing the melanoma cells. Our data suggest that melanoma invasion is associated with the formation of special channel-like structures, providing a new concept, structured tumour cell spreading. Altogether, these data provide potential new prognostic markers and therapeutic targets/strategies for preventing melanoma dissemination.