Feature selection is an important task in data mining and pattern recognition, especially for high-dimensional data. It aims to select a compact feature subset with the maximal discriminative capability. The discriminability of a feature subset requires that selected features have a high relevance to class labels, whereas the compactness demands a low redundancy within the selected feature subset. This paper defines a new feature redundancy measurement capable of accurately estimating mutual information between features with respect to the target class (MIFS-CR). Based on a relevance measure and this new redundancy measure, a multi-objective evolutionary algorithm with class-dependent redundancy for feature selection (MECY-FS) is presented. The MECY-FS algorithm employs the Pareto optimality to evaluate candidate feature subsets and finds compact feature subsets with both the maximal relevance and the minimal redundancy. Experiments on benchmark datasets are conducted to validate the effectiveness of the new redundancy measure, and the MECY-FS algorithm is verified to be able to generate compact feature subsets with a high predictive capability.