Nowadays, heuristics represent a commonly used alternative to solve complex optimization problems. This, however, has given rise to the problem of choosing the most effective heuristic for a given problem. In recent years, one of the most used strategies for this task has been the hyper-heuristics, which aim at selecting/generating heuristics to solve a wide range of optimization problems. Most of the existing selection hyper-heuristics attempt to recommend only one heuristic for a given instance. However, for some classes of problems, more than one heuristic can be suitable. With this premise, in this paper, we address this issue through an evolutionary multilabel learning approach for building hyper-heuristics. Unlike traditional approaches, in themultilabel formulation, the result could not be a single recommendation, but a set of potential heuristics. Due to the fact that cooperative coevolutionary algorithms allow us to divide the problem into several subproblems, it results in a natural approach for dealing with multilabel classification. The proposed cooperative coevolutionarymultilabel approach aims at choosing the most relevant patterns for each heuristic. For the experimental study included in this paper, we have used a set of constraint satisfaction problems as our study case. Our experimental results suggest that the proposed method is able to generate accurate hyper-heuristics that outperform reference methods.