In the IT industry, software systems with modular design are always desired as they are more comprehensible, maintainable, and thus better quality. However, as they are reused outside their original context, the modularity usually degrades over time. Software remodularization is a commonly applied software engineering technique that divides a system into independent packages (modules) having loose coupling and higher cohesion characteristics. Remodularization is generally challenging since sometimes cohesion and coupling quality parameters need to be adjusted against developer intuition. Therefore, in this paper, we propose a cost-effective software remodularization approach, which aims at improving package structure such that it adheres to the developer’s knowledge and expectations. The proposed approach works in three sequential phases. Firstly, it identifies various key information from the source code. Secondly, this extracted information is fused to represent more accurate dependency relations among different classes, and this fused information is used to construct a weighted directed graph at class-level. Finally, a newly proposed software remodularization algorithm (based on an n-state spin model called Potts Model) is used to perform clustering and obtain a remodularized solution of a software system. We also carried out an empirical evaluation of the proposed remodularization approach on four standard open-source Java systems. The obtained results are encouraging and justify the validity as proposed approach is capable of improving modularity by 11–39%.