In the Software Development Life-Cycle, the maintenance phase is often the most costly stage due to the efforts devoted to understanding the system. The Software Module Clustering Problem (SMCP) is an optimization problem which objective is to find the most modular organization of software systems to ease their comprehension. In this problem, software projects are frequently modeled as graphs. Then, the objective of the SMCP, which is proved to be $$backslashmathcalNbackslashmathcalP$$-hard, is to group the vertices in modules such that the modularity of the graph is maximized. In this work, we present an algorithm based on Variable Neighborhood Descent for the SMCP and study a novel quality metric, the Function of Complexity Balance, which was recently proposed for the problem. Our proposal has been favorably evaluated over a dataset of 34 real software projects, outperforming the previous state-of-the-art method, a Hybrid Genetic Algorithm, in terms of both quality and computing time. Furthermore, the results are statistically significant according to the Wilcoxon’s signed rank test.