Multi-label classification has been increasingly recognized since it can classify objects into multiple classes, simultaneously. However, its effectiveness might be sacrificed due to high dimensionality problem in feature space and sparseness problem in label space. To address these issues, this paper proposes a Two-Stage Dual Space Reduction (2SDSR) framework that transforms both feature space and label space into the lower-dimensional spaces. In our framework, the label space is transformed into reduced label space and then supervised dimensionality reduction method is applied to find a small number of features that maximizing dependency between features and that reduced labels. Using these reduced features and labels, a set of classification models are built. In this framework, we employ two well-known feature reduction methods such as MDDM and CCA, and two widely used label reduction methods i.e., PLST and BMD. However, it is possible to apply various dimensionality reduction methods into the framework. By a set of experiments on five real world datasets, the results indicated that our proposed framework can improve the classification performance, compared to the traditional dimensionality reduction approaches which reduce feature space or label space only.