Feature selection aims to eliminate unimportant and redundant features or to select effective and interacting features. It is a challenging task to accurately measure the relationships of candidate features, the selected features and categories in the selection process, especially for high-dimensional and small-sample-size data. To this end, a new measure named Dynamic Feature Importance (DFI) is proposed, as well as its corresponding feature selection algorithm named Dynamic Feature Importance based Feature Selection (DFIFS). In order to obtain higher classification accuracy with smaller number of features, a newly Modified-Dynamic Feature Importance based Feature Selection (M-DFIFS) algorithm is developed by combining DFIFS with classical filters. Based on experiments with 14 public high-dimensional datasets, the lately M-DFIFS algorithm shows significantly better performance than five typical filter algorithms in terms of their average accuracy with acceptable computing time. When using random forest as the classifier, M-DFIFS brings a great advantage in the number decrease of selected features. Hence the new feature selection framework “Filter + DFIFS” is verified very effective to solve problems of obtaining high accuracy with a few features. •A novel measure of the dynamic importance of features in the selection process.•A new feature selection algorithm based on Dynamic Feature Importance.•An effective “filter+proposed algorithm” based feature selection framework.•Smaller feature subset selected by proposed algorithm with high accuracy.•Good applicability to high-dimensional and small-sample-size data.