This paper introduces a new methodology to perform feature selection in multi-label classification problems. Unlike previous works based on the χ2 statistics, the proposed approach uses the multivariate mutual information criterion combined with a problem transformation and a pruning strategy.This allows us to consider the possible dependencies between the class labels and between the features during the feature selection process. A way to automatically set the pruning parameter is also proposed, based on the permutation test combined with a resampling strategy. Experiments carried out on both artificial and real-world datasets show the interest of our approach over existing methods.