Multi-label classification is a challenging task of assigning multiple labels to a single sample, which requires models to consider label correlations. The classifier chain approach, which models label dependencies sequentially, is an effective and efficient approach for multi-label classification. However, the classifier chain’s performance relies heavily on the order in which labels are arranged. Any error in the early part of the chain can propagate, leading to larger errors later, also known as error propagation. Optimising the label order is crucial but computationally difficult, as it is an NP-hard problem with a large search space and conflicting performance metrics. This paper proposes a novel algorithm, DECC, which uses Differential Evolution to optimise label order in classifier chains for multi-label classification. DECC represents candidate solutions as continuous vectors and employs a sorting mechanism to convert them into valid label orders. Two fitness functions, based on multiple multi-label performance metrics, are proposed, and the algorithm’s effectiveness is validated through experiments on ten real-world datasets. DECC demonstrates superior performance over existing genetic algorithm-based methods, offering a more flexible, efficient, and effective approach to optimising label order in multi-label classification.