In this paper, the authors propose a new steganographic scheme based on vector quantisation (VQ) and search-order coding (SOC). The capacity of the proposed scheme is higher than others based on VQ and the quality of stego-image is acceptive. In general, the capacity of the schemes based on VQ is usually 1-bit per block. In 2004, Yu et al. proposed a scheme to increase the capacity to 3-bit per pair of blocks. In the proposed scheme, the authors utilised multiple codebooks and chose the combinations of per pair of blocks, to embed the secret data. The capacity was increased to 6-bit per pair of blocks, and the quality was identical Yu et al.'s scheme.