Feature selection problems often appear in the application of data mining, which have been difficult to handle due to the NP-hard property of these problems. In this study, a simple but efficient hybrid feature selection method is proposed based on binary state transition algorithm and ReliefF, called ReliefF-BSTA. This method contains two phases: the filter phase and the wrapper phase. There are three aspects of advantages in this method. First, an initialization approach based on feature ranking is designed to make sure that the initial solution is not easy to get tapped into local optimum. Then, a probability substitute operator based on feature weights is developed to update the current solution according to the different mutation probabilities of the features. Finally, a new selection strategy based on relative dominance is presented to find the current best solution. The simple and efficient algorithm k-nearest neighborhood with the leave-one-out cross validation is used as a classifier to evaluate feature subset candidates. The experimental results indicate that the proposed method is more efficient in terms of the classification accuracy through a comparison to other feature selection methods using seven public datasets and several real biomedical datasets. For public datasets, the proposed method improved the classification average accuracy by about 2.5% compared with the filter method. For a specific biomedical dataset AID1284, the classification accuracy significantly increased from 77.24% to 85.25% by using the proposed method.