Multicriteria clustering problem has been studied and applied scarcely. When a multicriteria clustering problem is tackled with an outranking approach, it is necessary to include preferences of decision makers on the raw dataset, e.g., weights and thresholds of the evaluation criteria. Then, it is necessary to conduct a process to obtain a comprehensive model of preferences represented in a fuzzy or crisp outranking relation. Subsequently, the model can be exploited to derive a multicriteria clustering. This work presents an exhaustive search approach using a credibility similarity measure to exploit a fuzzy outranking relation to derive a multicriteria clustering. The work includes two experimental designs to evaluate the performance of the algorithm. Results show that the proposed method has good performance exploiting fuzzy outranking relations to create the clusterings.