In recent years, there have been rapid developments in various bioinformatics technologies, which have led to the accumulation of a large amount of biomedical data. The biomedical data can be analyzed to enhance assessment of at-risk patients and improve disease diagnosis, treatment, and prevention. However, these datasets usually have many features, which contain many irrelevant or redundant information. Feature selection is a solution that involves finding the optimal subset, which is known to be an NP problem because of the large search space. Considering this, a new feature selection approach based on Binary Chemical Reaction Optimization algorithm (BCRO) and k-Nearest Neighbors (KNN) classifier is presented in this paper. Tabu search is integrated with CRO framework to enhance local search capacity. KNN is adopted to evaluate the quality of selected candidate subset. The results for an experiment conducted on nine standard medical datasets demonstrate that the proposed approach outperforms other state-of-the-art methods.