Classified vector quantisation (CVQ) of images is a vector quantisation-based coding method for preserving perceptual features while retaining simple vector quantiser distortion measures during codebook design and encoding process. In the paper, a new algorithm for CVQ codebook design the ‘classified nearest neighbour clustering’ (CNNC) algorith, is presented. The CNNC algorithm is based on a classification process of small image blocks and on an agglomerative clustering algorithm, and is used to design simultaneously M codebooks for M different classes, defined for a CVQ system. The CNNC algorithm can be used with squared error and weighted squared error distortion measures employing one of two optimisation criteria which are presented and tested in the paper. In addition, fast search algorithm is presented aimed at reducing computational efforts encountered during codebook design. The CNNC algorithm is shown to provide a systematic and effective method for CVQ codebook design making CVQ more feasible and easy to implement.