An approach provides interdomain traversal to support packetized voice transmissions. A request is received and specifies a directory number for establishing a communication session from a first endpoint to a second endpoint. The first endpoint is behind a first network address translator of a first domain, and the second endpoint is within a second domain. A service provider network is accessed to determine a network address for communicating with the second endpoint based on the directory number, to determine existence of a second network address translator within the second domain, and to establish, if the network address can be determined, a media path between the first endpoint and the second endpoint based on the network address to support the communication session. An encrypted session is established with a proxy server according to a cryptographic protocol to support the media path. The proxy server resides within the second domain.