<p>Accurate and interpretable medical data classification is essential for supporting reliable clinical decision-making. Feature selection (FS) plays a critical role in this process by identifying the most informative attributes, thereby improving model efficiency and reducing complexity. However, conventional FS methods often suffer from premature convergence, limited exploration capability and difficulty in handling high-dimensional or imbalanced datasets. To address these challenges, this study introduces the Enhanced Hiking Optimization Algorithm (EHOA), an enhanced FS method that extends the original HOA with three key enhancements: chaotic map-based initialization to increase population diversity, a dynamically adaptive sweep mechanism to balance exploration and exploitation and velocity-inspired update rules to refine convergence behavior. A binary variant using an S-shaped transfer function is also developed for discrete FS problems. Comprehensive experiments were conducted on 33 benchmark datasets, including medical and gene expression data, using four different classifiers to ensure robustness and generalizability. Furthermore, a comparative evaluation on eight global optimization problems demonstrated the superior global search capability of EHOA. The proposed method achieved an average classification accuracy of 91.65% and 97.14% reduction in feature dimensionality, outperforming state-of-the-art FS methods. Statistical significance testing confirmed the reliability of these improvements, while performance metrics addressing data imbalance ensured fair evaluation. To enhance transparency, SHAP (SHapley Additive exPlanations) was applied for post-hoc interpretability, providing global and instance-level insights into feature relevance. Overall, EHOA offers an accurate, efficient and interpretable solution for complex medical data classification and holds strong potential for real-world clinical applications.</p>