A solution for the Network Address Translation (NAT) traversal problem for Real Time Protocol (RTP) is provided, which uses an RTP Proxy (e.g., a Session Border Controller (SBC)), instead of being logically located between the NAT and the Feature Server (FS), but instead, for devices which use a protocol unsupported by the SBC, having these devices first signal the Feature Server, which determines whether and how an RTP proxy should be invoked. An RTP proxy should be invoked by the FS if Both endpoints (e.g., devices) are behind different NATs (or one of the endpoints is behind a NAT and the other is not) and neither of the endpoints are already signaled through an RTP proxy. For example, the SBC is interposed (at least logically) between the Feature Server and other shared components.