The problem of reducing the bandwidth of a matrix consists of finding a permutation of rows and columns of a given matrix that keeps the non-zero elements in a band as close as possible to the main diagonal. This NP-complete problem can also be formulated as a vertex labelling problem on a graph, where each edge represents non-zero element of the matrix. For reducing the bandwidth of a matrix, we propose Variable neighborhood search based heuristic that successfully combines several recent ideas from the literature. Empirical results presented on the collection of 113 benchmark instances indicate that the proposed heuristic compares favorably to all previous methods. Moreover, with our approach, we found 26 new best solutions.