Background and Aims Colorectal cancer (CRC) is the third most commonly diagnosed malignancy and the second leading cause of cancer death worldwide. The latest guidelines recommend that all CRC patients need to be tested for microsatellite instability (MSI). MSI patients often have deficient mismatch repair (dMMR). The MSI/dMMR has been used as a biomarker for predicting the favorable response to immunotherapy and prognosis of patients. However, MSI signature genes and their relationship to tumor-infiltrating immune cells have not been fully described. Therefore, this study was conducted to discover novel MSI signature genes in CRC through machine learning and verify their diagnostic values and relationships with immune cell infiltration.Methods According to the inclusion and exclusion criteria, the GSE39582 dataset in GEO database was used as the training set, and the COAD dataset in TCGA database was used as the external validation set. Using machine learning methods (LASSO regression and SVM-RFE algorithm), MSI signature genes were screened in the GSE39582 CRC data set and validated in the TCGA COAD dataset. Receiver operating characteristic (ROC) curve and area under the curve (AUC) were used to evaluate the diagnostic performance of genes for MSI. The CIBERSORT algorithm evaluated each sample's immune infiltrating cell components, and Spearman correlation analysis was used to verify the relationship between MSI signature genes and immune cells.Results A total of 536 CRC patients were included in training set, of which 77 cases (for 14.37%) were high microsatellite instability (MSI-H). In validation set, there were a total of 389 CRC patients, of which 67 cases (17.22%) were MSI-H. The baseline data analysis showed that the TNM profiles and survival rates in MSI-H/dMMR CRC were superior to those in low microsatellite instability (MSI-L) or microsatellite stable (MSS)/proficient mismatch repair (pMMR) CRC (P<0.05). In GSE39582 dataset, 21 MSI signature genes were screened by LASSO regression, and 6 genes were screened by SVM-RFE algorithm. The MSI signature genes were identified as EIF5A, CXCL13, HNRNPL, HOXC6, RPL22L1, and Y16709 by combining the two algorithms. The diagnostic efficacy of MSI signature genes was further verified in TCGA database, and EIF5A was found to have the highest diagnostic efficacy. The AUC values for EIF5A in training and validation sets were 0.922 and 0.805, respectively. At the same time, Spearman correlation analysis found that EIF5A was mainly positively correlated with CD8⁺ T cells, activated dendritic cells, helper T cells, M1 macrophages, γδ T cells, and neutrophils; it was negatively correlated with CD4⁺ memory T cells, M2 macrophages, quiescent dendritic cells, eosinophils, and regulatory T cells.Conclusion Analysis of novel MSI signature genes in CRC shows that EIF5A has a good diagnostic performance and clinical value for CRC MSI status. It is also associated with immune cells and immune microenvironment. Thus, EIF5A may become a new marker for immune checkpoint therapy.