An efficient codebook search method for the EIA/TIA IS-54 vector-sum excited linear predictive (VSELP) speech coder is described. The method uses a two-stage search procedure. In the first stage, diagonal approximation of the correlation matrix of the filtered basis vectors is assumed and a simple sign detection procedure is used to identify a codeword which is close to the optimum codeword. In the second stage, a refinement search is carried out on those codewords which have a Hamming distance of one from the codeword obtained in the first stage. The new search procedure has a complexity only proportional to the bit rate which is much faster than the Gray code search employed in the IS-54 VSELP coder. Simulation results show that the SNR obtained using the proposed fast procedure is the same as that obtained in the standard VSELP coder.