Although side-match vector quantization (SMVQ) and its variants have been proposed to reduce the bit rate of coding images, the coding quality is decreased by it. The reason is that when a block is encoded in SMVQ, the side-match method uses only two neighboring blocks, (no edge information is available in the other two neighboring blocks) to predict the state of the codebook. We propose a new variable-rate finite state vector quantizer (VRFSVQ) to encode the blocks with a variable rate according to both the coding quality and the bit rate. The VRFSVQ can preencode all the blocks, allowing each block to employ more than two neighboring blocks to yield the state codebook. Furthermore, whereas users of SMVQ must specify the size of the state codebook before applying the side-match method to yield the state codebook, in the VRFSVQ the users do not need to specify the size of the state codebook for each encoding block. Experimental results indicate that the VRFSVQ has a high peak SNR and low bit rate for image coding.