An apparatus and a method for operating an exchange in order to support Network Address Translation (NAT) traversal in a Voice over Internet Protocol (VoIP) system are provided. In the method, when a setup request signal is received from a calling Internet phone, first mapping of an IP address and a User Datagram Protocol (UDP) port of the calling Internet phone to first embedded Media Proxy Solution (eMPS) IP address and UDP port is performed. A setup request of the calling Internet phone including the first eMPS IP address and UDP port information is relayed to a called Internet phone. A response signal including an IP address and an UDP port of the called Internet phone is received from the called Internet phone in response to the setup request. Second mapping of the IP address and UDP port of the called Internet phone to second eMPS address and UDP port is performed. A response signal including the second eMPS IP address and UDP port information is relayed to the calling Internet phone in response to the setup request.