Disclosed are methods and apparatus for handling data containing embedded addresses. In general terms, prior to transmission of data having an embedded address or port, an initiating host sends a NAT Probe to an end-host with which the initiating host wishes to communicate. The NAT Probe includes the embedded address or port and a type indicating that translation of the address and/or port is requested if needed. As the NAT Probe traverses through one or more NAT devices as it is transmitted to the end-host, each NAT device is enabled to recognize the NAT Probe type and translate the embedded address and/or port, depending upon the individual NAT device's configuration. When the NAT Probe reaches the final hop NAT device or end-host, a NAT Probe Reply is sent back to the initiating host. The NAT Probe Reply contains a translated embedded address and/or port which is compatible with the end-host's network. The NAT Probe Reply also contains a type which differs from the type of the NAT Probe. As the NAT Probe Reply traverses back through the same NAT devices, the NAT device recognize the type of the NAT Probe Reply and do not translate the embedded address and/or port.