For most of data sets, there exist some redundant, irrelevant and even noise features. Usually, there are plenty of features in medical data sets and the correlation among features is strong. So, feature selection of medical data sets gets great concern in recent years. RELIEFF is one of the effective feature selection algorithms, but cannot remove redundant features. RS is a mathematical approach to intelligent data analysis and can remove redundant features. So, the novel RS- RELIEFF feature selection algorithm is proposed in this paper. In RS-RELIEFF, feature reduction is applied in the data set with RS firstly, and then feature selection is applied with RELIEFF later, the new integrative weight of each condition feature will be got in the end. The novel proposed algorithm was tested in medical data sets. The experimental results show that the RS-RELIEFF algorithm has better classification accuracy 71.2644% and fewer selected features.