Many real applications involve optimisation problems where more than one objective has to be optimised at the same time. One of these kinds of problems is graph partitioning, that appears in applications such as VLSI design, data-mining, efficient disc storage of databases, etc. The problem of graph partitioning consists of dividing a graph into a given number of balanced and non-overlapping partitions while the cuts are minimised. Although different algorithms to solve this problem have been proposed, since this is an NP-complete problem, to get more efficient algorithms for increasing complex graphs still remains as an open question. In this paper, we present a new multilevel algorithm including a hybrid heuristic that is applied along the searching process. We also provide experimental results to demonstrate the efficiency of the new algorithm and compare our approach with other previously proposed efficient algorithms.