This paper describes a new segmentation and quantization technique for low bit-rate speech coders. Bit-rate reduction is achieved by combining segmentation and quantization, where a segment consists of one or more adjacent frames. The algorithm for selecting and quantizing segments from a pre-determined number of frames extends the frame-based trellis techniques. It models the input speech as a sequence of variable length segments with the option to interpolate frames in skipped segments. The new algorithm, denoted as Trellis Segmentation-Quantization (TSQ), reduces the bit-rate needed for spectral envelope representation, with only a small degradation in log-spectral distance values. Experimental results show that TSQ achieves a lower spectral distance than alternate frame transmission, matrix quantization and trellis based frame selection and interpolation.