This study proposes an Enhanced Binary Kepler Optimization Algorithm (BKOA-MUT) improves feature selection (FS) by integrating Kepler’s planetary motion laws with DE/rand and DE/best Mutation Approach. BKOA-MUT balances exploration and exploitation, effectively guiding search for optimal feature subsets. BKOA-MUT was evaluated using k-Nearest Neighbors (k-NN) and Support Vector Machine (SVM) on 25 UCI benchmarks, including three large-scale ones. It outperformed recent Meta-heuristic Algorithms (MHAs) in accuracy, feature reduction, and computational efficiency. The algorithm showed rapid convergence, minimal feature selection, and scalability, making it a robust and adaptable tool for enhancing FS in machine learning, validated through the Wilcoxon rank-sum test.