A method of establishing a connection traversing at least one network address translation (NAT) gateway is presented. In the method, a bind request is sent from a source device to a mediation element via a NAT gateway. A bind response associated with the bind request is received. A connection request is sent to the mediation element. The mediation element causes the connection request to be sent to a destination device. A connection response associated with the connection request is received. A hello message is sent to a predicted destination address. The predicted destination address is based on an address received in the connection response. A data connection is established between the source device and the destination device using the predicted destination address.