The present study aimed to identify molecules associated with lymphovascular invasion (LVI) and perineural invasion (PNI) and to examine their biological behavior in colorectal cancer (CRC). LVI- and PNI-associated molecules were identified and verified using sequential processes including (1) identification of 117 recurrence-associated genes differentially expressed on RNA-seq analysis using primary cancer tissues from 130 CRC patients with and without systemic recurrence; (2) analysis of molecules associated with LVI and PNI; (3) assessment of biological properties by measuring proliferation, anoikis, invasion/migration, epithelial-mesenchymal transition and autophagy flux; and (4) verification of disease-free survival using public datasets. Gelsolin (GSN) and 2'-5'-oligoadenylate synthetase 2 (OAS2) were associated with PNI and LVI, respectively. Invasion potential was >2-fold greater in GSN-overexpressing LoVo cells than in control cells (p<0.001-0.005), whereas OAS2-overexpressing RKO cells showed reduced invasion (p<0.001-0.005). GSN downregulated E-cadherin, β-catenin, claudin-1 and snail, and upregulated N-cadherin and ZEB1, whereas OAS2 overexpression had the opposite effects. Several autophagy-related proteins including ATG5-12, ATG6/BECN1, ATG7 and ATG101 were downregulated in GSN-overexpressing LoVo cells, whereas the opposite pattern was observed in OAS2-overexpressing RKO cells. Patients with low GSN expression had significantly higher 5-year recurrence-free survival (RFS) rates than those with GSN overexpression (73.6% vs. 64.7%, p = 0.038), whereas RFS was longer in patients with OAS2 overexpression than in those with underexpression (73.4% vs. 63.7%, p = 0.01). In conclusion, GSN and OAS2 were positively and negatively associated with recurrence, respectively, suggesting their potential value as predictors of recurrence or therapeutic targets in CRC patients.