This paper deals with the design and performance evaluation of a CELP codec at 3.5 kbit/s based on multi-path search methods. The rationale of this approach stems from the fact that delayed-decision coding algorithms outperform conventional techniques, in which the parameters to be transmitted are optimized sequentially. Tree codes have been applied to both the spectral information, quantized via a multi-stage vector quantizer, and the excitation codevectors, along with relative optimal gains. Preliminary results of this study show that the proposed scheme is a viable approach for achieving good speech quality at bit-rates below 4 kbit/s.