During various phases of software development lifecycle, the internal structure of the software degrades which finally results in increased maintenance efforts and hence cost. One quick solution to this problem is software remodularization in which restructuring of different software elements such as classes/ packages/ methods is done (without changing their original meaning and functionality). Several researchers have proposed different techniques for software remodularization. Each technique considers two points of view: dependency measurement among software elements (based on structural, conceptual and/or change history based relations) and performing clustering using different algorithms. So, in this paper, first of all, an empirical evaluation is carried out in order to test the role of different dependency relations in modeling dependency among different software elements. From an empirical evaluation, it is observed that the change history of a software system plays a major role in modeling dependency relations and hence must be used along with other relations for more accurate measures. Then, a new weighted dependency measurement scheme is proposed by combining structural, conceptual and change history based relations among software elements together, with more importance to evolutionary dependency relations. Finally, different dependency schemes are evaluated with six clustering algorithms by applying them to four standard open source Java software of variable sizes and belonging to different domains. The obtained results show that our proposed approach is capable of accurately determining dependence relations among various software elements as compared to other similar approaches present in literature and thus increases restructuring accuracy.