IP telephony systems are expected to be deployed worldwide in the near future because of their potential for integrating the multimedia communication infrastructure over IP networks. Phone-to-phone connection over an IP network via IP telephony gateways (IP-GWs) is a key feature of the system. In an IP telephony system, a low-bit-rate voice codec is used to improve bandwidth efficiency. However, due to the packet transfer method over the IP network, it is necessary to add packet headers, including IP, UDP, and RTP headers, which increases the header overhead and thus decreases transfer efficiency. Moreover, because there will be large numbers of short voice packets flowing into the IP network, the load on the Internet will increase. We propose voice stream multiplexing between IP-GWs to solve these problems. In this scheme, multiple voice streams are connected between a pair of IP-GWs, enabling multiplexed voice stream transfer. The voice stream multiplexing mechanism can reduce the header overhead as well as decrease the number of voice packets. The voice stream multiplexing we propose is to concatenate RTP packets destined for the same IP-GW at a multiplexing interval period into a single UDP packet. The advantage of this method is that no new additional header is required and the current well-defined H. 323 and RTP standards can be applied with minimum changes. We implemented and tested the system. The results show that the proposed method is effective at reducing both the header overhead and the number of packets. In a typical case, the bandwidth is cut by 40% for eight G. 723.1-encoded voice streams through header overhead reduction and the number of voice packets is also decreased to 1/8. Furthermore, this method can easily be enhanced to a general RTP packet multiplexing method that is applicable not only to an IP-GW but also to other RTP multiplexing and de-multiplexing applications.