Normalized cut is one of the most popular graph clustering criteria. The main approaches proposed for its resolution are spectral clustering methods (e.g. [1], [2]) and a multilevel approach of Dhillon, Guan and Kulis [3]. Their aim is to obtain good solutions in a small amount of time for large instances. Metaheuristics are general frameworks for stochastic searches often employed in global optimization to improve the solutions obtained by other heuristics. Variable Neighborhood Search (VNS) is a metaheuristic which exploits systematically the idea of neighborhood change during the search. In this paper, we propose a VNS heuristic for normalized cut segmentation. Computational experiments show that in most cases this VNS heuristic improves significantly, and in moderate time, the solutions obtained by the current state-of-the-art algorithms.