Colour image quantization is a data compression technique that reduces the total set of colours in an image to a representative subset. This problem is expressed as a large M-median one and the Variable Neighbourhood Search meta-heuristic, together with decomposition, is applied to solve it. Computational experience shows this ap- proach compares favorably with two other recent heuristics.