The graph partitioning problem consists of dividing the vertices of a graph into a set of balanced parts, such that the number of edges connecting vertices in different parts is minimised. The multilevel approaches reduce the size of the graph by successively matching vertices and edges until a small graph is built, which is divided into several parts. Then the graph is recursively uncoarsed by a simultaneous optimisation of the partitions. The complexity of the scientific applications where the graph partitioning problem appears, makes parallel processing very useful. In this paper we present a new parallel multilevel algorithm for graph partitioning, which is focused to explore different areas of the search space. This algorithm mixes heuristic techniques such as Simulated Annealing (SA), Tabu Search (TS) and elitist mechanisms of selection. The partitions obtained by our algorithm often improve the results of the corresponding serial version, and these provided by other previously proposed algorithms.