Multilabel classification is a challenging research problem in which each instance may belong to more than one class. Recently, a considerable amount of research has been concerned with the development of “good” multi-label learning methods. Despite the extensive research effort, many scientific challenges posed by e.g. highly imbalanced training sets and correlation among labels remain to be addressed. The aim of this paper is to use a heterogeneous ensemble of multi-label learners to simultaneously tackle both the sample imbalance and label correlation problems. This is different from the existing work in the sense that we are proposing to combine state-of-the-art multi-label methods by ensemble techniques instead of focusing on ensemble techniques within a multi-label learner. The proposed ensemble approach (EML) is applied to six publicly available multi-label data sets from various domains including computer vision, biology and text using several evaluation criteria. We validate the advocated approach experimentally and demonstrate that it yields significant performance gains when compared with state-of-the art multi-label methods.