The technological revolution has made available a large amount of data with many irrelevant and noisy features that alter the analysis process and increase time processing. Therefore, feature selection (FS) approaches are used to select the smallest subset of relevant features. Feature selection is viewed as an optimization process for which meta-heuristics have been successfully applied. Thus, in this paper, a new feature selection approach is proposed based on an enhanced version of the Capuchin search algorithm (CapSA). In the developed FS approach, named ECapSA, three modifications have been introduced to avoid a lack of diversity, and premature convergence of the basic CapSA: (1) The inertia weight is adjusted using the logistic map, (2) sine cosine acceleration coefficients are added to improve convergence, and (3) a stochastic learning strategy is used to add more diversity to the movement of Capuchin and a levy random walk. To demonstrate the performance of ECapSA, different datasets are used, and it is compared with other well-known FS methods. The results provide evidence of the superiority of ECapSA among the tested datasets and competitive methods in terms of performance metrics.