This paper presents a new Trellis Coded Vector Residual Quantizer (or TCVRQ) that combines trellis coding and vector residual quantization. The TCVRQ is a general-purpose sub-optimal Vector Quantizer with low computational costs and small memory requirement that permits high memory savings when compared to traditional quantizers. Experiments confirm that TCVRQ is a good compromise between memory/speed requirements and quality and that it is not sensitive to codebook design errors. A method is proposed for computing quantization levels and the performance of the TCVRQ when applied to speech coding at very low bit rates and to direct image coding is experimentally analyzed.