In the domains of data mining and machine learning, feature selection (FS) is an essential preprocessing step that has a significant effect on the machine learning model’s performance. The primary purpose of FS is to eliminate unnecessary features, resulting in time-space reduction as well as improved the corresponding learning model performance. Horse herd optimization algorithm (HOA) is a new metaheuristic algorithm that mimics the herding behavior of horses. Within a wrapper-based approach, a binary version of HOA is proposed in this study to select the optimal subset of features for classification purposes. The transfer function is the most important aspect of the binary version. Eight transfer functions, S-shaped and V-shaped, are tested to map the continuous search space into binary search space. Two main enhancements are integrated into the standard HOA to strengthen its performance. A Levy flight operator is added to improve the HOA’s exploring behavior and alleviate local minimal stagnation. Secondly, a local search algorithm is integrated to enhance the best solution obtained after each iteration of HOA. The purpose of the second enhancement is to increase the exploitation capability by looking for the most promising places discovered by HOA. Large-scaled, middle-scaled, and low-scaled datasets from reputable data repositories are used to validate the performance of the proposed algorithm (BinHOA). Comparative tests with state-of-the-art algorithms reveal that the Levy flight with the local search algorithm have a significant favorable impact on the performance of HOA. An enhancement of the population diversity is observed with avoidance of being trapped in local optima.