This paper presents a new vector quantization technique, called predictive residual vector quantization (PRVQ), which combines the concepts of predictive vector quantization (PVQ) and residual vector quantization (RVQ) to implement a high performance VQ scheme with low search complexity. A major task in the PRVQ design is the joint optimization of the vector predictor and the RVQ codebooks. In order to achieve this, a constrained optimization technique is introduced, which is then compared with a jointly designed technique and a closed loop design technique. Simulation results show the superiority of the proposed PRVQ scheme over the equivalent RVQ, PVQ and an unconstrained VQ scheme. The proposed PRVQ scheme gives the best performance when the predictor and all the stage quantizers are jointly optimized.