Large scale multi-label learning, i.e. the problem of determining the associated set of labels for an instance, is gaining relevance in recent years due to the emergence of several real-world applications. Most notably, the exponential growth of the SocialWeb where a resource can be labeled by millions of users using one or more tags, i.e. a resource can be associated to several labels at the same time. A well-known approach for multi-label classification is the Binary Relevance (BR) algorithm which trains a binary classifier for each label independently. However, the serial implementation of BR is not suitable for medium or large datasets due to the time and computational resources required for training. For example, training classifiers for mid-size datasets using MULAN implementation of BR might take several weeks. This paper discusses a parallel implementation of the MULAN BR technique that harnesses the computational power of nowadays multi-core processors. Our implementation presents a speed-up in the training phase of up to 12 times when compared to the original MULAN implementation. In addition, the cross-validation technique of MULAN had huge RAM requirements, making it unusable with large datasets. Therefore, we have overcome this limitation by using compact data structures and taking advantage of disk caching. We have also compared our implementation against scikit-learn, a popular tool for data mining and data analysis, showing significant improvements in speed-up.