In this paper, an efficient transcoding algorithm between G.723.1 and AMR speech coders is proposed for providing interoperability between IP and mobile networks. Transcoding is completed through three processing steps: line spectral pair (LSP) conversion, pitch interval conversion, and fast adaptive-codebook search. For maintaining minimum distortion, sensitive parameters to quality such as adaptive and fixed-codebooks are re-estimated from synthesized target signals. To reduce overall complexity, other parameters are directly converted in parametric levels without running through the complete decoding process. Objective and subjective preference tests verify that the proposed transcoding algorithm has equivalent quality to conventional tandem approach. In addition, the proposed algorithm achieves 20~40% reduction of the overall complexity over tandem approach with a shorter processing delay.