Regional lymph node metastasis negatively affects prognosis in colon cancer patients. The molecular processes leading to regional lymph node metastasis are only partially understood and proteomic markers for metastasis are still scarce. Therefore, a tissue-based proteomic approach was undertaken for identifying proteins associated with regional lymph node metastasis. Two complementary tissue-based proteomic methods have been employed. MALDI imaging was used for identifying small proteins (≤25 kDa) in situ and label-free quantitative proteomics was used for identifying larger proteins. A tissue cohort comprising primary colon tumours without metastasis (UICC II, pN0, n = 21) and with lymph node metastasis (UICC III, pN2, n = 33) was analysed. Subsequent validation of identified proteins was done by immunohistochemical staining on an independent tissue cohort consisting of primary colon tumour specimens (n = 168). MALDI imaging yielded ten discriminating m/z species, and label-free quantitative proteomics 28 proteins. Two MALDI imaging-derived candidate proteins (FXYD3 and S100A11) and one from the label-free quantitative proteomics (GSTM3) were validated on the independent tissue cohort. All three markers correlated significantly with regional lymph node metastasis: FXYD3 (p = 0.0110), S100A11 (p = 0.0071), and GSTM3 (p = 0.0173). FXYD3 and S100A11 were more highly expressed in UICC II patient tumour tissues. GSTM3 was more highly expressed in UICC III patient tumour tissues. By our tissue-based proteomic approach, we could identify a large panel of proteins which are associated with regional lymph node metastasis and which have not been described so far. Here we show that novel markers for regional lymp.