A system and method, e.g., Voice Proxy Server (VPS), is described for managing Voice over IP (VoIP) services between a NAT enabled private network and a public network such as the Internet. The VPS acts like the Call Agent to the nodes in the private network and it represents an embedded voice client to the real Call Agent in the public network. Each logical line of the VPS corresponds to a real voice line in the private node. VoIP signaling messages may be carried in the payload of the IP packets. VPS will properly translate IP address and/or port number information in the payload to correctly route the signaling data between networks. Additionally, VPS will forward the incoming Real Time Protocol (RTP) packets to the real destination in the private network.