Mesh partitioning is an important problem that has extensive applications in many areas. Multilevel algorithms are a successful class of optimization techniques which addresses the mesh partitioning problem. In this paper we present an enhancement of the technique that uses nature inspired metaheuristic to achieve higher quality partitions. We apply and study a multilevel ant-colony (MACO) optimization, which is a relatively new metaheuristic search technique for solving optimization problems. The MACO algorithm performed very well and is superior to classical k-METIS and Chaco algorithms. Furthermore, it is even comparable to combined evolutionary/multilevel scheme used in JOSTLE evolutionary algorithm. Our MACO algorithm returned also some solutions that are better then currently available solutions in the Graph Partitioning Archive.