Bandwidth scarcity and data confidentiality are big constraints for internet application development. In order to transmit an image along with secret data over the internet efficiently, a compression-based, reversible information hiding scheme can be used to achieve data concealment as well as data compression. Therefore, using this kind of scheme is advantageous when bandwidth and confidentiality are major concerns of the users. In this study, we propose a novel, reversible information hiding scheme for vector quantisation (VQ)-encoded images. The proposed encoding scheme uses a given value to decide the embedding capacity of secret data in an image, and produces either a VQ-encoded image or a compressed codestream as the output. The embedded secret data and the original VQ-encoded image can be extracted from the output when needed. The proposed scheme utilises the fact that two adjacent blocks in a VQencoded image are usually similar: First, it uses codebook re-ordering based on the similarity to the codeword of the first block in an image. Second, it calculates the difference of the new indices of two adjacent image blocks. Finally, it encodes the secret bits along with the difference value as the compressed output for each block. We conducted several experiments and then used several representative images as the input to compare the proposed scheme with other related works. The results showed that the proposed scheme is very efficient in terms of bit rate, particularly when the input image has many similar neighbouring blocks in it.