This study presents a new steganographic method that embeds secret data into a cover digital image using VQ encoding. The core concept of the proposed method uses the gradient adjacent prediction (GAP) algorithm, which enhances prediction accuracy of neighboring blocks in SMVQ encoding. To embed secret data into the cover image, the proposed method utilizes the features of GAP to decide the capacity of the secret data per pixel in a block. It then embeds the secret data accordingly. It also embeds an index value in each block to ensure that the secret data can be recovered back. The index value points to the closest codeword of a state codebook to the encoding block, where the state codebook is generated by GAP-based SMVQ. The result shows that the proposed method has better performance than a recent similar work proposed by Chen and Lin in 2010.